贪心
为什么选择贪心?
~~除了数据结构和dp剩下的都是贪心模拟暴力~~
1) 状态不好设计，如P1016，每个加油站的加油量要精确到小数后两位，基本无法枚举，并且原题具有贪心选择性，即局部最优解能推出全局最优解，这样就用贪心。
2) 枚举量过大，如CF939E,如果dp就是\(O(n^2)\),但发现性质后尺取法就是\(O(n)\);再如CF47E也是尺取法，如果暴力就是\(O(n^2)\)
有些枚举量过大的问题还可以用数据结构维护。
P1080
$$假设已经排了几个人（包括国王），设他们左手上的数的乘积为S.\
现在要给2个人排序，记第一个人左手上的数为a_{1}，右手上的数为b_{1}；第二个人左手上的数为a_{2}，右手上的数为b_{2}。\ 如果第一个人排在前面优于第二个人排在前面，那么\ max(S/b_1,S∗a_1/b_2)<max(S/b_2,S∗a_2/b_1)\
显然有S/b_2\leq S* a_1/b_2\
假设有S a_1/b_2\geq S a_2/b_1,则max(S/b_1,S∗a_1/b_2)\geq max(S/b_2,S∗a_2/b_1),矛盾。\
所以S a_1/b_2<S a_2/b_1,整理得a_1 b_1<a_2 b_2\
所以只需要按照a* b排序即可。 $$
- 结论：对于贪心选择性的证明，可以假设一个中间状态，即已经做完\(i-1\)个人,考虑第\(i\)个位置可以放的人，为了证明方便可以只考虑2个或少量的人,像P3951一样。
CF939E
贪心尺取法。
有两条重要性质。
1) 对于一个加入的新数一定要选。
$$ 原式 ans=Max-\frac{sum}{n}\
考虑用新的最大替换掉原来的最大，设新的最大比原来最大大 \Delta(x)\ ans=\frac{(Max+\Delta(x))\times n-(sum+\Delta(x))}{n}\
因为 n\geq 1，ans一定变大（优秀） $$ 2) 对于集合 s 剩下的数，一定是选前面几个小的数，并且选的数的个数是单调不减的。
可以意会一下证明，一定是选比当前集合平均数小的数加进来，使平均数更小，答案才会变得更大。 $$ 原式 ans=Max-\frac{sum}{n}\
考虑新加一个数 \Delta(x)\ 新的式子 ans=Max-\frac{sum+\Delta(x)}{n+1}\
若新式减去原式>0，则新式更优秀\ 新式减原式得\ -\frac{sum+\Delta(x)}{n+1}+\frac{sum}{n}\
等于\ \frac{sum-n\times \Delta(x)}{n\times(n+1)}>0\
得出更优秀条件为：sum-n\times \Delta(x)>0，即 \Delta(x) <\frac{sum}{n}\ $$
证毕，可以用尺取法。
#include<iostream>
#include<cstdio>
#include<cstring>
#define db double
#define int long long
using namespace std;
const int N=5e5+10;
int n,cnt,tot;
int vis[N],q[N];
db res[N],a[N],sum[N];
int read1(){
int x=0,f=1;
char ch=getchar();
while(ch>'9' || ch<'0'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch<='9' && ch>='0'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
void work(){
int l=1,r=0;
db ans=-1.0;
for(int i=1;i<=cnt;++i)sum[i]=sum[i-1]+a[i];
for(int i=1;i<=cnt;++i){
if(!vis[i])continue;
ans=-1.0;
while(l<=i){
db tmp=(double)(a[i]-(double)(sum[l]+a[i])/(l+1));
if(tmp>ans)ans=tmp,++l;
else{
--l;
break;
}
}
if(l==i+1)--l;
res[i]=ans;
}
for(int i=1;i<=tot;++i)printf("%.10lf\n",res[q[i]]);
}
signed main(){
cnt=0,tot=0;
n=read1();
for(int i=1,op;i<=n;++i){
op=read1();
if(op==1){
a[++cnt]=(double)read1();
}else{
vis[cnt]=1;
q[++tot]=cnt;
}
}
work();
return 0;
}
P1645
贪心的将序列按照右端点排序，那么每个区间内应该选的点应该分布在它的最右边，这样能够保证有的点最少，是最优解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=2e3+10;
int n,ans;
int vis[N];
struct query{
int l,r,m;
}q[N];
int w[N][N];
bool cmp(query a,query b){
return a.r<b.r;
}
signed main(){
memset(vis,0,sizeof vis);
memset(w,0,sizeof w);
scanf("%lld",&n);
for(int i=1;i<=n;++i){
scanf("%lld%lld%lld",&q[i].l,&q[i].r,&q[i].m);
}
sort(q+1,q+n+1,cmp);
for(int i=1;i<=n;++i){
for(int j=q[i].l;j<=q[i].r;++j){
w[j][++w[j][0]]=i;
}
}
int ans=0;
for(int i=1;i<=n;++i){
int l=q[i].l,r=q[i].r,m=q[i].m;
if(!q[i].m)continue;
for(int j=r;j>=l;--j){
if(!q[i].m)break;
if(vis[j])continue;
vis[j]=1;
ans++;
//q[i].m--;
for(int k=1;k<=w[j][0];++k){
if(q[w[j][k]].m)q[w[j][k]].m--;
}
}
}
printf("%lld",ans);
return 0;
}
/*
2
1 1000 1000
1 999 999
*/
P1191
将每一列前n-1行往上能数到的最多的点数记录下来，那么每个第n行的点的贡献就是从左往右扫并取最小值。
一个数扫描\(O(n)\),共\(n^2\)个数，所以总复杂度\(O(n^3)\)
P1016
1.只要存在一个加油站与下一个加油站或终点间的距离大于\(c* d_2\),那么无解.
2.对于每个加油站，有两种可能：
1）他能到达的所有点中有价格比他小的加油站，那就加油到刚好能到达那个加油站，此时油量会变为零；
2）他能到达的点里没有价格小于它的加油站，那就在这里充满油，再到后面那些加油站中价格相对最小的加油站，油量从$c \(减少\)(\Delta d)/d_2 $。
证明：
1.1）中会不会剩余的油量已经能满足能够到达下一加油站？
不会，因为它由上一个加油站转移过来，而上一个加油站最远能到的距离到不了目标加油站，因此一定会再加油，不会由不加油就走了的情况。
2.2）中为什么要选价格相对最少的加油站，并且要充满油？
因为如果再后面的加油站能够到达比它小的加油站，那么他会需要加油来到达那一加油站，这是就可以用之前价格低的油，达到最优；就算没有，为了到达终点也要加油，所以选择相对最小的补充油量。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=210,INF=1050;
double d1,c,p0,d2;
int n;
struct node{
double d,p;
}q[N];
bool cmp(node a,node b){
return a.d<b.d;
}
int main(){
scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p0,&n);
q[0].d=0,q[0].p=p0;
for(int i=1;i<=n;++i){
scanf("%lf%lf",&q[i].d,&q[i].p);
}
sort(q+1,q+n+1,cmp);
q[n+1].d=d1,q[n+1].p=0;
for(int i=1;i<=n+1;++i){
if(q[i].d-q[i-1].d>c*d2){
printf("No Solution");
return 0;
}
}
int pos=0;double cc=0;double ans=0;
while(pos<n+1){
int tmp=0,loc=n+1,col=n+1;
double minn=INF;
for(int i=pos+1;i<=n+1;++i){
if(c<(q[i].d-q[pos].d)/d2){
loc=i-1;
break;
}
}
for(int i=pos+1;i<=loc;++i){
if(minn>q[i].p){
minn=q[i].p;
col=i;
}
if(q[i].p<=q[pos].p){
tmp=i;
break;
}
}
if(tmp)ans+=(((q[tmp].d-q[pos].d)/d2)-cc)*q[pos].p,cc=0,pos=tmp;// delta must bigger than cc
else ans+=(c-cc)*q[pos].p,cc=c-(q[col].d-q[pos].d)/d2,pos=col;
}
printf("%.2lf",ans);
return 0;
}
P1658
假设当前手中的硬币能够组成1,2,...,sum这些面值，此时sum<x.
那么考虑添加一种硬币，使得sum变大。
当当前硬币的值为a时，能组成的最大面值由sum变成sum+a.
但是，如果a>sum+1,那么sum+1,sum+2,...,a-1这些数就不能组成，那么面值就不连续了.
所以我们要取a<=sum+1且a最大。
无解的情况就是没有1。
注意取a时要用upper_bound-1,不能用lower_bound-1. 考虑:
5 7 此时都求出了5，正确；
5 6 7 此时upper_bound求出6，正确;lower_bound求出5，错误.
code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,x;
int a[N];
bool cmp(int a,int b){
return a<b;
}
int main(){
scanf("%d%d",&x,&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
sort(a+1,a+n+1,cmp);
if(a[1]!=1){
printf("-1");
return 0;
}
int sum=0,cnt=0;
while(sum<x){
int tmp=upper_bound(a+1,a+n+1,sum+1)-a-1;
sum+=a[tmp];
cnt++;
}
printf("%d",cnt);
return 0;
}
P1248
这题的坑点就是\(B\)车间不能同时处理多个物件，要堆到后面逐个处理。
首先考虑每次的贡献：
设\(fa\)为\(a\)车间的处理时间，\(fb\)为\(b\)车间的处理时间，则：
因为只有第\(i\)个\(a\)物件和第\(i-1\)个\(b\)物件都做完才能做第\(i\)个\(b\)物件。
再考虑\(a\)车间已经做了\(P\)时间的工作，不考虑\(b\)车间剩余的物件，此时还剩两件。
那么\(1\)在前和\(2\)在前的贡献分别是：
如果1更优，就有
但这个式子不能直接做题，反例是能举出来的。
我们考虑两(三)种情况：
1) \(a_i<=b_i\)，则有\(a_1<a_2\) 1) \(a_i>b_i\)，则有\(b_1>b_2\)
又考虑\(a_1>b_1,a_2<b_2\)时一定不会满足上述式子，所以只需要保证\(a_1<b_1,a_2>b_2\),即\(a<b\)的放在前面，\(a>b\)的放在后面即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n;
struct node{
int a,b,d,id;
}s[N];
bool cmp(node a,node b){
if(a.d==b.d){
if(a.d<=0)return a.a<b.a;
else return a.b>b.b;
}
return a.d<b.d;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&s[i].a);
for(int i=1;i<=n;++i)scanf("%d",&s[i].b);
for(int i=1;i<=n;++i)s[i].d=s[i].a==s[i].b?0:(s[i].a>s[i].b?1:-1),s[i].id=i;
sort(s+1,s+n+1,cmp);
int fa=0,fb=0;
for(int i=1;i<=n;++i){
fb=max(fa+s[i].a,fb)+s[i].b;
fa+=s[i].a;
}
printf("%d\n",fb);
for(int i=1;i<=n;++i)printf("%d ",s[i].id);
return 0;
}
UVA11300
当面对这种看似每种操作都没有方向，~~很像模拟退火~~的题，就先强行规定一个方向。
注意到一个人给别人钱和别人给它钱的次数没有限制，所以设\(x_i\)表示后一个人给前一个人的钱数，负数表示逆方向给钱。
所以有:
注意\(A_n\)那个式子就没有用了。
消去除\(x_1\)所有的未知量，整理可得：
所以这个问题就变成了坐标轴上\(n-1\)个点，选那个位置使得所有的点到这个位置的距离和最短。
此时输出中位数即可，贪心的证明很巧妙，~~但我懒，略~~
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e6+10;
int c[N];
int n,a,tot,ans;
bool cmp(int a,int b){
return a<b;
}
int abs1(int a){
return a>=0?a:-a;
}
signed main(){
while(scanf("%lld",&n)!=EOF){
tot=0,ans=0;
for(int i=1;i<=n;++i)scanf("%lld",&a),c[i]=c[i-1]+a,tot+=a;
tot/=n;
for(int i=1;i<=n;++i)c[i]-=i*tot;
sort(c+1,c+n+1,cmp);
int mid=n/2+1;
for(int i=1;i<=n;++i){
ans+=abs1(c[i]-c[mid]);
}
printf("%lld\n",ans);
}
return 0;
}