洛谷 P4379 [USACO18OPEN]Lemonade Line
2024-08-23 20:17:25
题目描述
这是农场上一个炎热的夏日,Farmer John要给他的 NN 头奶牛发柠檬汽水了!所有的 NN 头奶牛(方便起见,编号为 1 \dots N1…N )都喜欢柠檬汽水,只是有些喜欢的程度更高一些。具体地说,奶牛 ii 为了获得柠檬汽水最多愿意排在w_iwi 头奶牛之后。现在所有的 NN 头奶牛都在田里,但是只要Farmer John敲响牛铃,这些奶牛就会立刻赶到FJ的柠檬汽水站。她们会在FJ开始分发柠檬汽水之前到达,但是没有两头奶牛会在同一时刻到达。此外,当奶牛 ii 到达时,当且仅当至多有 w_iwi 头奶牛在排队时她会来排队。
Farmer John想要提前准备一定量的柠檬汽水,但是他不想浪费。排队的奶牛的数量可能取决于她们到达的顺序。帮助他求出最少可能的排队的奶牛数量。
输入输出格式
输入格式:
第一行包含 NN ,第二行包含 NN 个用空格分隔的整数 w_1, w_2, \dots, w_Nw1,w2,…,wN 。输入保证 1 \leq N \leq 10^51≤N≤105 ,此外对于每头奶牛 ii , 0 \leq w_i \leq 10^90≤wi≤109 。
输出格式:
输出在所有可能的奶牛到达顺序之下,最小可能的排队的奶牛数量。
输入输出样例
说明
在这个情况下,可能最后仅有三头奶牛在队伍中(这也是最小可能值)。假设 w = 7w=7 和 w = 400w=400 的奶牛先到并等在队伍中。然后 w = 1w=1 的奶牛到达并且会离开,这是由于已经有2头奶牛在队伍中了。然后 w = 2w=2 的两头奶牛到达,一头留下排队,一头离开。
供题:Dhruv Rohatgi
思路:贪心即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,tot;
int a[MAXN];
int cmp(int a,int b){
return a>b;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
sort(a+,a++n,cmp);
for(int i=;i<=n;i++){
if(tot<=a[i]) tot++;
else break;
}
cout<<tot;
}
最新文章
- 【九度OJ】题目1111:单词替换
- UIWebView用法详解及代码分享
- uva 11186 Circum Triangle<;叉积>;
- windows 下 文件属性及目录列表操作
- node-webkit:开发桌面+WEB混合型应用的神器
- RSA PKCS1padding 填充模式
- oracle触发器应用
- KEIL C51 中嵌入汇编以及C51与A51间的相互调用
- boost.asio系列——buffer
- aspnet5安装ef7备忘
- Java对【JSON数据的解析】--fastjson解析法
- 秒表计时器以及Stopwatch
- 关系型数据库工作原理-数据库查询器(翻译自Coding-Geek文章)
- php添加日志文件
- Java通过JDBC连接数据库的三种方式!!!并对数据库实现增删改查
- pytest+request 接口自动化测试
- mysql中什么是逻辑备份
- Camera’s Depth Texture
- Javascript 行为委托
- Vue 父组件传值到子组件
热门文章
- nginx访问php程序相关配置
- sql server查看某个表上的触发器
- 建设一个能承受500万PV/每天的网站如果计算?
- 飞思卡尔开发板-迅为IMX6开兼容单核 双核 四核Plus开发板
- Leetcode_638.Shopping Offers
- HDU_3792_(素数筛+树状数组)
- Dynamic type checking and runtime type information
- jQuery 首页搜索区域模块随页面滑动而变化
- PowerDesigner连接MySQL数据库
- 解决dom4j加载xml文件性能慢的问题