P4090 [USACO17DEC]Greedy Gift Takers
2024-08-27 08:52:39
题目链接
题意分析
首先 如果当前序列中一头奶牛拿不到礼物的话
那么他后面的奶牛也拿不到礼物
所以我们可以二分
由于可以操作无限次
所以我们对于当前\([1,mid)\)的奶牛按照\(c\)值排序之后
贪心的先放\(c\)中最小的奶牛
如果依然存在一头奶牛被放在\(mid\)之前
那么就无法使\(mid\)得到礼物
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 108611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int n,ans;
int num[M],tmp[M];
IL bool check(int mid)
{
if(mid==1) return 1;
for(R int i=1;i<mid;++i) tmp[i]=num[i];
sort(tmp+1,tmp+mid);
int now=n-mid;
for(R int i=1;i<mid;++i)
{
if(tmp[i]>now) return 0;
++now;
}
return 1;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);
for(R int i=1;i<=n;++i) read(num[i]);
int le=1,ri=n;ans=-1;
while(le<=ri)
{
int mid=(le+ri)>>1;
if(check(mid)) le=mid+1,ans=mid;
else ri=mid-1;
}
printf("%d\n",n-ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
最新文章
- 原生js实现查询天气的小应用
- 谈谈UI架构设计的演化
- 常用的JS HTML DOM 事件
- Java利用aspose-words将word文档转换成pdf(破解 无水印)
- arpg网页游戏之地图(四)
- 使用proxool 连接池:No suitable driver found for proxool
- Linux下安装MySQLdb模块
- A Pretty Good Splash Screen in C#
- makefile的简单写法
- cocos2d的安装
- List GroupBy真实用法,Reflection(反射)用法,Enum用法,正则,搜索下拉布局
- salt上编写了备份日志的脚本
- BZOJ3322[Scoi2013]摩托车交易——最大生成树+贪心+倍增
- BZOJ3505 CQOI2014数三角形(组合数学)
- JVM运行时内存区域
- java程序源码
- Spark 调优(转)
- java、oracle对CLOB处理
- C# 分享几个ip的方法吧,包括正则验证ip
- python添加Windows环境变量
热门文章
- Window Application has ";update"; key words
- [SoapUI]怎样运用Schema通过*.xsd文件来验证response对应的xml文件
- FPGA时序约束和timequest timing analyzer
- HBase-1.2.1和Phoenix-4.7.0分布式安装指南
- (转)C# .net微信开发,开发认证,关注触发消息,自动应答,事件响应,自定义菜单
- VR眼镜和AR眼镜的区别
- FIREDAC的TFDJSONDataSets和TFDJSONDeltas查询和提交数据
- SSO单点登录三种情况的实现方式详解(转载)
- iperf命令 +speedtest-cli
- 关于 Kafka offset