P2672 推销员
下面讲正确的贪心
题解
考虑当推销员要推销 i 家客户时,他可以有两种选择:
(1)选择前 i 家疲劳值 a 最大的客户,加上这些客户里最远的距离
(2)选择前 i-1 家疲劳值 a 最大的客户,然后从后边找一个距离最远的客户
所以贪心思路就出来了
考虑维护什么?
反正怎样都是与疲劳值息息相关,那不如先按照疲劳值从大到小sort一下好了
then
sum[ i ] 前 i 个疲劳值最大的客户,疲劳值之和
x[ i ] 前 i 个疲劳值最大的客户中(也就是sum[ i ]中),距离起点最远的那个客户的距离
hou[ i ] (sort之后)后 i 个客户中单独推销最大的那个客户的 单推值(=距离*2+疲劳值)
对于每一个 i ,ans就是:
max(sum[ i-1 ]+hou[ i ] , sum[ i ]+q[ i ])
代码
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int n; int sum[maxn],hou[maxn],x[maxn]; struct node { int s,a; }peo[maxn]; bool cmp(node x,node y) { return x.a >y.a ; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&peo[i].s ); for(int i=1;i<=n;i++) scanf("%d",&peo[i].a ); sort(peo+1,peo+n+1,cmp); for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+peo[i].a ; x[i]=max(x[i-1],peo[i].s*2 ); } for(int i=n;i>=1;i--) hou[i]=max(hou[i+1],peo[i].s*2+peo[i].a ); for(int i=1;i<=n;i++) { printf("%d ",max(sum[i-1]+hou[i],sum[i]+x[i])); } return 0; }
后记
带坏萌新
这题数据好水啊,一个错误的贪心井然可以AC
一个nice数据可以卡死这个错误代码
有Bug:测试数据为:5 1 2 4 2 5 5 4 4 3 2
正确输出:12 17 21 25 28
下面这个程序的输出:12 17 21 24 28
代码
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int n,k,rode; long long ans=0; struct node { int s,a,dt; }peo[maxn]; bool cmp(node x,node y) { return x.a >y.a ; } int main() { scanf("%d ",&n); if(n==1) { int x,y; scanf("%d ",x*2+y); return 0; } for(int i=1;i<=n;i++) scanf("%d",&peo[i].s ); for(int i=1;i<=n;i++) { scanf("%d",&peo[i].a ); peo[i].dt =peo[i].s *2+peo[i].a ; if(peo[i].dt>ans) { ans=peo[i].dt ; k=i; } } printf("%ld ",ans); rode=peo[k].s; peo[k].a =-1; sort(peo+1,peo+n+1,cmp); for(int i=1;i<n;i++) { if(peo[i].s <=rode ) { ans+=peo[i].a ; printf("%ld ",ans); } else { ans+=peo[i].a ; ans-=rode*2; ans+=peo[i].s *2; rode=peo[i].s ; printf("%ld ",ans); } } return 0; }