上海计算机学会2020年4月月赛C++丙组T5吃苹果
发布时间
阅读量：
阅读量
题目描述
小爱共有n个苹果，并为每个苹果都设定了一定的有效期限。具体而言，在第i个位置对应的数值为ai天。当ai等于零时，则该位置对应的苹果必须立即食用以避免变质；而如果ai大于零，则表示该位置对应的苹果可以在其保质期内正常保存。
小爱每天只能吃一只苹果，她应该如何安排，使得吃到的苹果最多？
（22年9月24日：修改了题面，使题意更好理解，题目没有变化）
输入格式
第一行：单个整数 n；
第二行：n 个整数 a1,a2,⋯,an。
输出格式
单个整数：表示能够吃掉的最多的苹果数。
数据范围
- 对于 30% 的数据，1≤n≤10；
- 对于 60% 的数据，1≤n≤1,000；
- 对于 100% 的数据，1≤n≤1,000,000，0≤ai<n。
样例数据
输入:
5
4 1 0 2 1
输出:
4
具体实现方法是通过桶排序对苹果的保质期进行分类处理。对于具有i天保质期的苹果，在其保质期内存在可食用的日子时，则将其进行相应的处理操作。具体实现细节可参考代码部分。
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
int n;
int ans=0;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
a[t]++;//a[t]为保质期为t天的苹果有几个
}
for (int i=1;i<=n;i++)//循环每一天
{
ans+=a[i-1];//没过期的争取都吃掉
if (ans>i){//如果超过了天数，则每天吃一个，吃满。
ans=i;
}
}
printf("%d",ans);
return 0;
}全部评论 (0)
还没有任何评论哟~