[USACO 2018 Ope S]Lemonade Line

NC24281. [USACO 2018 Ope S]Lemonade Line

描述

这是农场上一个炎热的夏日，Farmer John要给他的N头奶牛发柠檬汽水了！所有的N头奶牛（方便起见，编号为1…N）都喜欢柠檬汽水，只是有些喜欢的程度更高一些。具体地说，奶牛i为了获得柠檬汽水最多愿意排在wi头奶牛之后。现在所有的N头奶牛都在田里，但是只要Farmer John敲响牛铃，这些奶牛就会立刻赶到FJ的柠檬汽水站。她们会在FJ开始分发柠檬汽水之前到达，但是没有两头奶牛会在同一时刻到达。此外，当奶牛i到达时，当且仅当至多有wi头奶牛在排队时她会来排队。

Farmer John想要提前准备一定量的柠檬汽水，但是他不想浪费。排队的奶牛的数量可能取决于她们到达的顺序。帮助他求出最少可能的排队的奶牛数量。

输入描述

第一行包含N，第二行包含N个用空格分隔的整数w1,w2,…,wN。输入保证1≤N≤100,000，此外对于每头奶牛i，0≤wi≤1000,000,000。

输出描述

输出在所有可能的奶牛到达顺序之下，最小可能的排队的奶牛数量。

示例1

输入:

5
7 1 400 2 2

输出:

说明:

在这个情况下，可能最后仅有三头奶牛在队伍中（这也是最小可能值）。假设w=7和w=400的奶牛先到并等在队伍中。然后w=1的奶牛到达并且会离开，这是由于已经有2头奶牛在队伍中了。然后w=2的两头奶牛到达，一头留下排队，一头离开。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 504K, 提交时间: 2019-06-23 14:25:51

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int n;
	long long w[100086];
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&w[i]);
	sort(w,w+n,cmp);
	int cnt=0;
	while(w[cnt]>=cnt)	cnt++;
	cout<<cnt;
}

C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 720K, 提交时间: 2020-02-17 22:11:41

#include<bits/stdc++.h>
using namespace std;
int a[100001],n,i,num;
int main()
{
	cin>>n;
	for(i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+n+1);
	while(a[n]>=num)
	{
		n--;
		num++;
	 } 
	 cout<<num;
}

Python3(3.5.2) 解法, 执行用时: 43ms, 内存消耗: 4704K, 提交时间: 2019-06-23 17:47:44

n = int(input())
w = list(map(int, input().split()))
w.sort(reverse=True)
# print(w)
print(sum(w[i] >= i for i in range(len(w))))