查看CodeForces/441B的源代码 ←CodeForces/441B

[[分类:贪心]]
==摘要==
{{信息题|Valera and Fruits|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70537#problem/A|1|100|time=2015-02-23 19:07:55}}
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70537 2015 Winter Warm up div1] A题
*原题链接：http://codeforces.com/problemset/problem/441/B
==题意==
n棵果树，每棵树可以再第<m>a_i</m>或<m>a_i+1</m>天采集总共<m>b_i</m>的蔬果，每天最多采集<m>v</m>的水果，问最多能采集到多少水果。
==题解==
按时间排序果树，遍历每一天，尽量采集先采集比较老（<m>a_i+1</m>）天的的水果，再采集新鲜的，按照这种贪心策略即可。

==代码==
{{折叠|441B.cpp代码已折叠
|<pre>
#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;
}
</pre>
|code441B}}