洛谷 P4379 [USACO18OPEN]Lemonade Line

2021年09月15日 阅读数:4
这篇文章主要向大家介绍洛谷 P4379 [USACO18OPEN]Lemonade Line,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目描述

这是农场上一个炎热的夏日,Farmer John要给他的 NN 头奶牛发柠檬汽水了!全部的 NN 头奶牛(方便起见,编号为 1 \dots N1N )都喜欢柠檬汽水,只是有些喜欢的程度更高一些。具体地说,奶牛 ii 为了得到柠檬汽水最多愿意排在w_iwi 头奶牛以后。如今全部的 NN 头奶牛都在田里,可是只要Farmer John敲响牛铃,这些奶牛就会马上赶到FJ的柠檬汽水站。她们会在FJ开始分发柠檬汽水以前到达,可是没有两头奶牛会在同一时刻到达。此外,当奶牛 ii 到达时,当且仅当至多有 w_iwi 头奶牛在排队时她会来排队。ios

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

输入输出格式

输入格式:

 

第一行包含 NN ,第二行包含 NN 个用空格分隔的整数 w_1, w_2, \dots, w_Nw1,w2,,wN 。输入保证 1 \leq N \leq 10^51N105 ,此外对于每头奶牛 ii , 0 \leq w_i \leq 10^90wi109 。spa

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 复制
5
7 1 400 2 2
输出样例#1: 复制
3

说明

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

供题:Dhruv Rohatgiit

思路:贪心便可。io

#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=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(tot<=a[i])    tot++;
        else break;
    }
    cout<<tot;
}

 

细雨斜风做晓寒。淡烟疏柳媚晴滩。入淮清洛渐漫漫。 雪沫乳花浮午盏,蓼茸蒿笋试春盘。人间有味是清欢。