CodeForces/441B 2015年2月24日 (二) 17:50云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
Valera and Fruits	★☆☆☆☆	答案正确	100	2015-02-23 19:07:55	无

• 来自寒假练习：2015 Winter Warm up div1 A题
• 原题链接：http://codeforces.com/problemset/problem/441/B

题意

n棵果树，每棵树可以再第或天采集总共的蔬果，每天最多采集的水果，问最多能采集到多少水果。

题解

按时间排序果树，遍历每一天，尽量采集先采集比较老（）天的的水果，再采集新鲜的，按照这种贪心策略即可。

代码

441B.cpp代码已折叠 展开折叠内容

#include <iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> #include<cstring> #include<climits> #include<queue> #include<vector> using namespace std; #define f(i,n) for(int i=1;i<=n;++i) #define fi(i,t,n)for(int i=t;i<=n;++i) #define fd(i,n) for(int i=n;i>=1;--i) #define fdi(i,t,n) for(int i=n;i>=t;--i) #define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i) #define rforeach(i,s) for(typeof(s.rbegin()) i=s.rbegin();i!=s.rend();++i) #define si(n) scanf("%d",&n) #define dsi(n) int n;scanf("%d",&n) #define llu unsigned long long #define lld long long #define ci const int & class st{public: int fruit,day; friend bool operator <(const st &a,const st&b){return a.day<b.day;} } a[3010]; int c[3010]={}; int main() { int n,v,ans=0; cin>>n>>v; f(i,n) { cin>>a[i].day>>a[i].fruit; } sort(a+1,a+n+1); f(i,n) { if(c[a[i].day]+a[i].fruit>=v) { a[i].fruit-=v-c[a[i].day]; ans+=v-c[a[i].day]; c[a[i].day]=v; }else{ c[a[i].day]+=a[i].fruit; ans+=a[i].fruit; a[i].fruit=0; } if(c[a[i].day+1]+a[i].fruit>=v) { a[i].fruit-=v-c[a[i].day+1]; ans+=v-c[a[i].day+1]; c[a[i].day+1]=v; }else{ c[a[i].day+1]+=a[i].fruit; ans+=a[i].fruit; a[i].fruit=0; } } cout<<ans; }