（以“分类:贪心 ==摘要== {{信息题|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}}...”为内容创建页面） |
小 （→题解： 写错） |
||
| 第7行： | 第7行： | ||
n棵果树，每棵树可以再第<m>a_i</m>或<m>a_i+1</m>天采集总共<m>b_i</m>的蔬果，每天最多采集<m>v</m>的水果，问最多能采集到多少水果。 | n棵果树，每棵树可以再第<m>a_i</m>或<m>a_i+1</m>天采集总共<m>b_i</m>的蔬果，每天最多采集<m>v</m>的水果，问最多能采集到多少水果。 | ||
==题解== | ==题解== | ||
| − | 按时间排序果树，遍历每一天，尽量采集先采集比较老（<m> | + | 按时间排序果树，遍历每一天，尽量采集先采集比较老（<m>a_i+1</m>）天的的水果，再采集新鲜的，按照这种贪心策略即可。 |
| + | |||
==代码== | ==代码== | ||
{{折叠|441B.cpp代码已折叠 | {{折叠|441B.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| Valera and Fruits | ★☆☆☆☆ | 答案正确 | 100 | 2015-02-23 19:07:55 | 无 |
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;
}
|
CloudLunar