贪心
树下
2018-09-19 20:59:40
# 贪心专题
### P1031 均分纸牌
这是一个比较水的贪心题目
1.先计算出牌堆平均数
2.进行一次从左至右的判断，牌堆数是否等于平均数
3.如果多则移至右侧牌堆，少则从右侧牌堆移动来进行填补
```
#include<cstdio>
using namespace std;
int n,count,tot;
int a[105];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
{scanf("%d",&a[i]);tot+=a[i];}
tot/=n;
for(int i=1;i<n;i++)
{
if(a[i]!=tot) count++;
a[i+1]=a[i+1]-(tot-a[i]);
a[i]=n;
}
printf("%d",count);
}
```
------------
### P1316 丢瓶盖
这是一个二分答案，比较裸，其中也是用了贪心思想的。
```
#include<bits/stdc++.h>
using namespace std;
int inf=0x7fffffff,n,m,l=0,r=inf,mid,now,tot;//一定要将inf定为2147483647
int a[100001];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
while(l<r){
mid=(l+r+1)>>1;//多用位运算，快
now=a[1];
tot=1;
for(int i=2;i<=n;i++){
if(a[i]-now>=mid)
now=a[i],tot++;
if(tot>=m)
break;
}
if(tot<m)
r=mid-1;
else
l=mid;
}
printf("%d",l);
}
```
------------
### P1369 矩形
运用了一下前缀和思想，也放在贪心专题里面好了。将矩形边上的点都记录下来，然后用前缀和来存一下边上的点的数量，最后一遍筛下来就完成了。整个题数据不大，直接暴力查找就好了。
```
#include<bits/stdc++.h>
using namespace std;
int x,xx=100,y,yy=100,l,m,n,sum,ans;
bool a[101][101];//定义一个bool就足够记录点的位置了，要习惯行节约空间，放MLE
int b[101][101],c[101][101];
int main(){
scanf("%d",&l);
for(int i=1;i<=l;i++){
scanf("%d%d",&m,&n);
a[m][n]=true;
x=max(x,m);
xx=min(xx,m);
y=max(y,n);
yy=min(yy,n);
}
for(int i=xx;i<=x;i++)
for(int j=yy;j<=y;j++)
b[i][j]=b[i][j-1]+a[i][j];
for(int i=xx;i<=x;i++)
for(int j=yy;j<=y;j++)
c[i][j]=c[i-1][j]+a[i][j];//记录边上的点的个数
for(int i=xx;i<=x;i++)
for(int j=yy;j<=y;j++)
for(int k=i+1;k<=x;k++)
for(int h=j+1;h<=y;h++){
sum=b[i][h]-b[i][j]+b[k][h]-b[k][j]+c[k][j]-c[i][j]+c[k][h]-c[i][h];
if(a[k][h])
sum--;//特判一下，判重
ans=max(ans,sum);//取一下最大值
}
printf("%d",ans);
}
```
------------
### P1525 关押罪犯
最小生成树的一个变形，其中运用了贪心的思想。将边从大到小排序，每次选取最大的边进行比较，如果能放到没有与他有矛盾的监狱就可以避免冲突，那么直到放不了为止，选取最大的输出即可。
```
#include<bits/stdc++.h>
using namespace std;
int n,m,r1,r2;
int father[20005],b[20005];
struct sjy{
int x,y,z;
}a[100005];//结构体定义（sjy函数助我AC）
template <class sjy>
inline void read(sjy &x){
sjy f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
x*=f;
}//快读
int cmp(const sjy&a,const sjy&b){
if(a.z>b.z) return 1;
return 0;
}//cmp排序
int find(int x){
if(father[x]!=x) father[x]=find(father[x]);
return father[x];
}//并查集的主要思想，寻找自己的父亲节点，就是找爸爸。
int main(){
read(n),read(m);
for(int i=1;i<=m;i++)
read(a[i].x),read(a[i].y),read(a[i].z);
for(int i=1;i<=n;i++)
father[i]=i;//将自己赋为自己的父亲节点
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++){
r1=find(a[i].x),r2=find(a[i].y);//寻找自己的父节点
if(r1==r2){
printf("%d",a[i].z);
return 0;
}//找不到可以放的监狱可以用了，就直接输出
if(!b[a[i].x])
b[a[i].x]=a[i].y;
else
father[find(b[a[i].x])]=find(a[i].y);
if(!b[a[i].y])
b[a[i].y]=a[i].x;
else
father[find(b[a[i].y])]=find(a[i].x);
}
printf("0");//记住特判一下
}
```
------------
### P1565 牛宫
单调栈+动态规划+前缀和+二分
其中的前缀和是贪心的一种思想
```
#include<bits/stdc++.h>
using namespace std;
long long n,m,x,len,ans;
long long a[201][201],f[201],sta[201];
template <class sjy>
inline void read(sjy &x){
sjy f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
x*=f;
}
long long findd(long long u){
long long l=1,r=len,tot=-1;
while(l<=r){
long long mid=(l+r)>>1;
if(sta[mid]<u)
r=mid-1,tot=mid;
else
l=mid+1;
}
return tot;
}
int main(){
read(n),read(m);
for(long long i=1;i<=n;i++)
for(long long j=1;j<=m;j++){
read(x);
a[i][j]=a[i][j-1]+x;
}
for(long long i=1;i<=m;i++)
for(long long j=1;j<=m;j++){
long long area=0;
sta[0]=1e10;
len=0;
for(long long k=1;k<=n;k++){
area+=a[k][j]-a[k][i-1];
if(area>0) ans=max(ans,k*(j-i+1));
else{
int z=findd(area);
if(z!=-1)
ans=max(ans,(j-i+1)*(k-f[z]));
}
if(sta[len]>area)
sta[++len]=area,f[len]=k;
}
}
printf("%lld\n",ans);
}
```
------------
### P1645 序列
将数列的顺序倒过来，从后往前筛会有不一样的答案，固定住后端点尽量满足后区间的条件
```
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[30005],ans;
struct sjy{
int l,r,v;
}a[30005];
int cmp(sjy a,sjy b){
return a.r<b.r;
}
int main(){
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v);
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++){
int cnt=0;
for(int j=a[i].l;j<=a[i].r;j++)
if(vis[j])
cnt++;
if(cnt<a[i].v)
for(int j=a[i].r;j>=a[i].l;j--)//从后往前筛
if(!vis[j]){
cnt++;
ans++;
vis[j]=1;
if(cnt==a[i].v)
break;
}
}
printf("%d",ans);
}
```