USACO2018 open Silver Problem 2

中文翻译:

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

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

输入格式(文件名:lemonade.in):

第一行包含N N,第二行包含N N个用空格分隔的整数w 1 ,w 2 ,…,w N w1,w2,…,wN。输入保证1≤N≤10 5 1≤N≤105,此外对于每头奶牛i i,0≤w i ≤10 9 0≤wi≤109。

输出格式(文件名:lemonade.out):

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

输入样例:
5
7 1 400 2 2

输出样例:
3

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

供题:Dhruv Rohatgi

官方题解:

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

int N, W[100000];

int main(void)
{
  ifstream fin("lemonade.in");
  ofstream fout("lemonade.out");

  fin >> N;
  for (int i=0; i<N; i++) fin >> W[i];

  sort(W,W+N);

  int i, num_in_line=0;
  for (i=N-1; i>=0; i--) {
    if (W[i] < num_in_line) break;
    num_in_line++;
  }

  fout << num_in_line << "\n";

  return 0;
}
全部评论

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务