摘要

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

题意

n棵果树,每棵树可以再第a_ia_i+1天采集总共b_i的蔬果,每天最多采集v的水果,问最多能采集到多少水果。

题解

按时间排序果树,遍历每一天,尽量采集先采集比较老(a_i+1)天的的水果,再采集新鲜的,按照这种贪心策略即可。

代码

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;
}

著作权声明[编辑]

关于[编辑]