P4379 [USACO18OPEN]Lemonade Line-白红宇

P4379 [USACO18OPEN]Lemonade Line

阅读量：5291 次

发布时间：2019-06-14

本文共 1058 字，大约阅读时间需要 3 分钟。

如有乱码，请。

题目描述

这是农场上一个炎热的夏日，Farmer John要给他的 $\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。$

输出格式

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

输入输出样例

输入 #1复制

57 1 400 2 2

输出 #1复制

说明/提示

在这个情况下，可能最后仅有三头奶牛在队伍中（这也是最小可能值）。假设

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int a[100610],n;inline bool cmp(int x,int y){ return x>y;}int main(){ scanf("%d",&n); for(int i=0;i

转载于:https://www.cnblogs.com/xiongchongwen/p/11507996.html

你可能感兴趣的文章