[Daimayuan] nice party(C++,二分,贪心)

news/2024/2/28 9:44:18

cc准备举办一场派对,他希望邀请他的朋友们过来参加,并且每个人都能玩得开心

cc有 n n n 位朋友,第 i i i 位的身价为 i i i

如果第 i i i 位朋友参加派对,并且玩得开心,当且仅当派对上至多有 X i X_i Xi 个人比他身价严格大于他,至多有 Y i Y_i Yi 个人身价严格小于他

cc想知道,他最多能邀请来多少人,并且他们每个人都玩得开心

输入描述

1 1 1 行给出一个数 T T T ,表示有 T T T,( 1 ≤ T ≤ 1 0 4 1≤T≤10^4 1T104) 组数据

对于每一组数据

1 1 1 行给出一个数 n n n,( 1 ≤ ∑ n ≤ 2 × 1 0 5 1≤∑n≤2×10^5 1n2×105),表示有 n n n 个朋友

接下来 n n n 行,每一行给出两个数 X i X_i Xi Y i Y_i Yi,( 0 ≤ X i , Y i < n 0≤X_i,Y_i<n 0Xi,Yi<n)

输出描述

输出一个数,表示cc所能邀请的最多的人的人数

样例输入

3
3
1 2
2 1
1 1
2
0 0
0 1
2
1 0
0 1

样例输出

2
1
2

解题思路

根据题意,我们有这样一种直觉:

所想邀请的人数越多,越不容易成功;

所想邀请的人数越少,越容易成功。

所以我们采用二分搜索:

int bin_search() {int l = 0, r = n + 1, mid;while (l + 1 != r) {mid = l + r >> 1;if (judge(mid)) l = mid;else r = mid;}return l;
}

但是如何judge(mid)是否符合题意呢?

考虑一种通常的情况:

我们遍历每一个人,现在遍历到第i个。

对于他,我们已知其前面已选择了cnt个人。

1)如果这个人不能来参加聚会,那么就简单跳过即可;

2)如果这个人能够参加聚会,且mid是符合题意的,那么在其之后至少还会再选择mid-cnt-1个人。

bool judge(int x) {int cnt = 0;for (int i = 1; i <= n; i++) {if (cnt <= ys[i] && x - cnt - 1 <= xs[i]) cnt++;}return x <= cnt;
}

然后我们来解决两个可能存在的疑问:

1)按照如上的统计方式,我们最后得到的cnt可能大于x,这会导致之前判断条件mid-cnt-1失去意义。

这个问题对结果没有影响,把多余的人删去就可以了。

2)按照如上的贪心算法,我们的统计结果不一定是最大的cnt,因为可能前面选择的人数过多,导致更多的人不再符合条件cnt <= ys[i]

进行贪心证明:

假设存在组合,使得在不选前面cnt个人的情况下,所选的人数能够变为cnt+k

那么根据已知条件,我们选择cnt+k个人中靠前的cnt个人,显然把他们替换为之前的cnt个人后仍然能够符合题意。

所以假设不成立。

最后,AC代码如下:

#include <iostream>
using namespace std;
const int max_n = 2e5;int xs[max_n + 1], ys[max_n + 1];
int n;bool judge(int x) {int cnt = 0;for (int i = 1; i <= n; i++) {if (cnt <= ys[i] && x - cnt - 1 <= xs[i]) cnt++;}return x <= cnt;
}int bin_search() {int l = 0, r = n + 1, mid;while (l + 1 != r) {mid = l + r >> 1;if (judge(mid)) l = mid;else r = mid;}return l;
}int main() {int t;cin >> t;while (t--) {cin >> n;for (int i = 1; i <= n; i++) cin >> xs[i] >> ys[i];cout << bin_search() << endl;}return 0;
}

http://www.ppmy.cn/news/363649.html

相关文章

泛娱乐社交(一)直播产品商业化解决方案

摘要 在过去几年的直播行业创业风口期中&#xff0c;直播的用户关注度疯狂增长&#xff0c;但用户质量却参差不齐。随着用户新鲜感一过&#xff0c;流失率变得相当严重&#xff0c;各大平台都在竭尽全力防御。然而&#xff0c;留住“凑热闹”的非直播受众用户并不是最关键的问…

中阳期货龙舟赛跟踪和监控系统

上篇文章说了中阳期货龙舟赛计时的编程&#xff0c;那么下面给大家分享一下使用OpenCV库跟踪和监控系统。 跟踪和监控系统&#xff1a;通过船上的GPS设备和网络技术实时跟踪纪录龙舟在赛道上的位置&#xff0c;其中可利用传感器获取龙舟的方向、速度和姿态等信息&#xff0c;以…

探索智慧文旅:沉浸式VR导览与个性化数字人带你畅游景区

导语&#xff1a; 随着科技的不断进步和智能化的兴起&#xff0c;智慧文旅已经成为旅游业的新趋势。在这个数字化时代&#xff0c;旅游体验已经不再局限于传统的观光和游玩&#xff0c;而是通过创新科技为游客提供了全新的旅行方式和更加丰富的体验。 在智慧文旅中&#xff0c…

HTML的导航栏的代码@沁宁

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>导航栏</title><style>.box{height:40px;border-top: 3px solid red;border-bottom: 1px solid lightpink;text-align: center;}.box a{wi…

织梦内核风吟导航QQ导航天下网址管理源码

简介&#xff1a; 织梦的内核&#xff0c;搭建没有毛病&#xff0c;估计应该有加密。 输入网址自动获取网站信息&#xff0c;免去复制粘贴。 响应式&#xff0c;自动适应手机版 导入数据库、修改data\common.inc.php这个数据库配置文件 后台/admin 账号密码均为admin 网盘下载…

Laysns内核仿qq技术网址导航网整站源码

介绍&#xff1a; Laysns内核仿qq技术网址导航网整站源码基于laysns开发&#xff0c;打包的也只是模板文件&#xff0c;使用前需要自行下载安装laysns主程序&#xff0c;然后再将模板文件夹上传到template文件夹下替换即可使用。 程序模板使用html5css3开发&#xff0c;必须在…

好看的个人qq主页-导航页源码

简介&#xff1a; 1.源码来自于joe主题群大?分享 2.与其他的导航页不一样&#xff0c;此源码效仿了QQ个人主页的模板 3.虽然不是很全面但是整体上看起来还不错&#xff0c;我搭建来看了看&#xff0c;作者是一个叫做苏云的大佬制作的&#xff0c;为什么是大佬因为我第一款导航…

为什么打开edge浏览器,就出来qq导航,hao123页面等等!

为什么打开edge浏览器&#xff0c;就出来qq导航&#xff0c;hao123页面等等&#xff01; 如图所示&#xff1a;打开是QQ导航&#xff0c;关键在于你的电脑里面有类似于电脑管家这样的软件&#xff0c;这就使得你打开浏览器之后&#xff0c;他会强制将你的浏览器启动页面设置为…

技术导航网站源码_qq技术导航_小刀娱乐网源码

今天给大家带来的是2020最新版QQ技术导航网源码&#xff0c;包含各大QQ技术网站qq技术导航&#xff0c;类似于小刀娱乐网的一个源码。 小刀娱乐网源码是aspaccess/mssql架构网站系统&#xff0c;电脑版&#xff0c;手机版&#xff0c;平板版无缝切换&#xff0c;一个后台同步管…

制作qq会员页面导航

制作qq会员页面导航 我在网上搜了很多帮助文档&#xff0c;样式设计都没有做得很好的&#xff0c;CSS样式设计都做得不够完美&#xff0c;这个是我总结了很多别人的经验和自己的经验出来的&#xff0c;希望对大家有所帮助&#xff0c;谢谢。 // 这个是最终结果图&#xff1a; …

仿QQ导航菜单(javascript)

<html> <head> <meta http-equiv"Content-Type" content"text/html; charsetgb2312"> <title>仿QQ导航菜单&#xff0d;www.51windows.Net</title> <style type"text/css"> .titleStyle{ background-color:…

仿QQ微信的底部导航

新人创作 高手勿喷&#xff01; 实现思路&#xff1a;通过点击某个按钮&#xff0c;跳出framelayout界面&#xff0c;实现界面切换。 什么都不用说了看代码&#xff1a; 1、新建布局文件 activity_test.xml <?xml version"1.0" encoding"utf-8"?&g…

Android仿QQ微信开场导航

相信大家对于微信等社交应用的UI界面已经都很熟悉了&#xff0c;该UI最值得借鉴的莫过于第一次使用的时候一些列产品介绍的图片&#xff0c;可以左右滑动浏览&#xff0c;最后进入应用&#xff0c;这一效果适用于多种项目中&#xff0c;相信今后开发应用一定会用得到。网路上也…

用html做qq会员页面导航,练习1:QQ会员页面导航.html

练习1&#xff1a;QQ会员页面导航 *{ margin: 0px; padding: 0px; } body a:link{ color: white; text-decoration: none; } body a:hover{ color:blue; text-decoration: underline; } li{ list-style: none; display: inline-block; vertical-align: middle; } ul{ backgroun…

仿 QQ 底部 tab 导航

仿 QQ 底部 tab 导航 原文链接&#xff1a; http://www.jianshu.com/p/826d730bd841 本篇博客主要实现以下效果&#xff1a; 使用 FragmentTabHost 实现 qq 底部 Tab 切换 使用 RadioGroup 和 RadioButton 实现仿 qq 底部切换 使用 RadioGroup 和 ViewPager 实现可以滑动切换的…

网站QQ导航

<a href"http://wpa.qq.com/msgrd?v3&uin[colorRed]361983679[/color]&siteqq&menuyes" target"_blank"><img border"0" title"单击联系站长苏飞" alt"单击联系站长苏飞" src"http://wpa.qq.com…

自己写的仿QQ空间导航栏

<!doctype html> <html> <head> <meta charset"utf-8"> <title>无标题文档</title> <style type"text/css"> *{ margin:0; padding:0; } .wrap{ width:900px; padding:0; margin:0 auto; border:1px solid #999…

32、用html制作QQ会员页面导航(半成品,需要素材)

<!DOCTYPE html> <html><head><meta charset"utf-8"><title>制作QQ会员页面导航</title><style type"text/css">*{margin: 0px auto;padding: 0px;}div{margin: 10px;color: white;width: 100%;height: 50px;ba…

仿qq底部Tab导航

本篇博客主要实现以下效果&#xff1a; 使用FragmentTabHost实现qq底部Tab切换使用RadioGroup和RadioButton实现仿qq底部切换使用RadioGroup和ViewPager 实现可以滑动切换的仿qq底部Tab切换解决Fragment多次实例化的几种方案Fragemnt的懒加载&#xff08;网上很多人称之为Frag…
最新文章