首页 > 代码库 > noip推荐系列:汽艇[贪心]

noip推荐系列:汽艇[贪心]

【问题背景】

  一天sxc,zsx,wl到gly坐汽艇,本来和其他的人约好了一起去,结果被放了鸽子,3人便只有一人负担x元去坐汽艇(很贵哦)。坐了才发现如果汽艇上人多了位置就不宽敞,就不好玩了。而3个人貌似是最好玩的,但究竟是不是呢? 

【问题描述】    假设有n个人要去坐1个汽艇,每个人单独坐汽艇的快乐程度是Ci,每多一个人,他的快乐程度会减去Di,请求出使快乐程度之和达到最大的方案。(假设汽艇的容量足够大)。 

【文件输入】 

  输入文件共有3行:    第1行是一个整数n;    第2行有n个整数,依次表示每个人单独坐汽艇的快乐程度Ci(1<=Ci<=10000);    第3行有n个整数,依次表示每多1人,每个人快乐程度的下降值Di(1<=Di<=10)。 

【文件输出】 

  应输出两行:    第1行一个整数,是最大的快乐程度之和;    第2行一个整数,是最大的快乐程度之和所对应的汽艇上的人数(若有多种方案,则输出人数最多的)。 

【样例输入】 

6

10 10 10 10 10 9

2 2 2 2 2 3

【样例输出】 

18

3

【样例说明】    前3个人去坐汽艇可使快乐程度之和达到最大,每个人的快乐程度均为10-2*2=6,总和是18。 

【数据范围】    对于30%的数据,n<=20;    对于100%的数据,n<=1000。

 

这样的题很容易可以判断出是贪心,DP不行,因为这题要考虑后效性;(而且个人感觉暴力都不好写)

但是怎么贪心?

这题我第一测的时候全WA= =,或许是因为写贪心已经形成一种定式了吧,总想着先排序,然后再乱搞什么的。

所以这题也算是给我一个教训吧

 

说说这题的思路吧

首先,我们不可以一下子判断出来选谁最优对吧

因为快乐值大的,下降值可有可能很大。同理。

所以,我们每选一次就判断一次谁最优;

其实很简单...(我比较傻逼没有想到)

不过就是模拟+贪心思想;

我们枚举坐汽艇的人数i,算出在当前人数i下,每一个人剩下的快乐程度,排序,算出i人最大的快乐程度总和;

再更新出答案即可;

 

附上代码:

 

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int maxn=1001;int n,m;struct node{	int c,d;}a[maxn];int f[maxn];int ans,tot=1;bool cmp(int x,int y){return x>y?1:0;}int main(){	//freopen("data.txt","r",stdin);	freopen("launch.in","r",stdin);	freopen("launch.out","w",stdout);	scanf("%d",&n);	for(int i=1;i<=n;i++) scanf("%d",&a[i].c),ans=max(ans,a[i].c);	for(int i=1;i<=n;i++) scanf("%d",&a[i].d);	for(int i=1;i<=n;i++){	    int temp=0;		for(int j=1;j<=n;j++) f[j]=a[j].c-(i-1)*a[j].d;		sort(f+1,f+n+1,cmp);		for(int j=1;j<=i;j++){			temp+=f[j];		}			if(ans<=temp){			ans=temp;			tot=i;		}	}	cout<<ans<<"\n"<<tot;	return 0;}

 

  

 

 

noip推荐系列:汽艇[贪心]