锐客网

  1. 首页 > it技术 > >

# 2019 GDUT Rating Contest #I A. The Bucket List

题解

2019 GDUT Rating Contest #I A. The Bucket List 题目见 ：
http://codeforces.com/group/NVaJtLaLjS/contest/238166/problem/A
题目大意： n头牛，每头牛i需要在一定时间内（si~ti）使用bi个桶，求总共最少使用多少个桶。
思路： 找到所有同一时间内最多使用的桶数目即是总共使用的桶数目。
一次优化： 【# 2019 GDUT Rating Contest #I A. The Bucket List】使用差分，f[i]为差分数组，即可在O(n)时间内求出所有时间中最多使用的桶数目。
实现：

#include #include #include using namespace std; int main() { int f[1008]; //差分数组 int n,s,t,d,i,j,maxt=0,ans=0; scanf("%d",&n); for (i=0; i<=1000; i++) f[i]=0; //初始化差分数组 for (i=1; i<=n; i++) { scanf("%d %d %d",&s,&t,&d); f[s]+=d; f[t+1]-=d; maxt=max(t,maxt); } for (i=1; i<=maxt; i++) { f[i]+=f[i-1]; ans=max(ans,f[i]); } printf("%d\n",ans); return 0; }

    推荐阅读


    上一篇：【保姆级】大佬手把手教你python+Opencv完成人脸解锁

    下一篇：Java中导入/导出excel|Java中导入/导出excel,导出pdf报表信息