＜贪心算法＞

前言：在主包还没有接触算法的时候，就常听人提起“贪心”，当时是layman，根本不知道说的是什么，以为很难呢，但去了解一下，发现也不过如此嘛（bushi)，还以为是什么高级东西呢（开个玩笑，本蒟蒻只会点基础的）。本篇以一道简单题引入，不懂算法也会哦

题目：拼数  NC16783

思路： 本蒟蒻开始想当然了，以为直接以字符串从大到小排拼接起来就好了（有没有人和我一样），但没考虑全面。如特殊例子，A="321",B="32",若只按字符串大小拼接，则答案为“32132”，但正确答案应该是“32321”，所以还应该比较拼接后的大小，返回大的那一个

错误代码：

#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(string a,string b){return a>b;
}
int main(){int n,i;string s[25];cin>>n;for(i=0;i<n;i++) cin>>s[i];sort(s,s+n,cmp);for(i=0;i<n;i++){cout<<s[i];}return 0;
}

正确代码：

#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(string a,string b){return a+b>b+a;
}
int main(){int n,i;string s[25];cin>>n;for(i=0;i<n;i++) cin>>s[i];sort(s,s+n,cmp);for(i=0;i<n;i++){cout<<s[i];}return 0;
}

再来做一题感受一下吧

题目：华华听月月唱歌 NC23036

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int> >pd;
int main(){int n,m,l,r,i,c=1;cin>>n>>m;for(i=0;i<m;i++){cin>>l>>r;pd.push_back({l,r});}sort(pd.begin(),pd.end());     //pair类型先按第一个元素排序,相等再按第二个if(pd[0].first!=1){  //若开头不是1,肯定不能修复cout<<-1;return 0;}l=1,r=1;for(i=0;i<m;i++){if(pd[i].first<=l){     //同一片段选终点最大的r=max(r,pd[i].second);}else{      //新的片段if(pd[i].first>r+1){   //不连续cout<<-1;return 0;}c++;l=r+1;  //新的l为上一段终点+1r=max(r,pd[i].second);   //更新r }if(r>=n){     //！！！及时结束！！！break;}} if(r<n){cout<<-1;return 0;}cout<<c;return 0;
}

贪心算法是一种在每一步选择中都采取当前状态下最优（如最小，最大…）的选择，从而希望导致结果是全局最优的算法，所以常常需要对元素进行排序（之前的最小生成树，Dijkstra算法求最短路径等就有利用）。

但贪心算法并不是对所有问题都适用。它只能在满足贪心选择性质和最优子结构性质的问题中有效。贪心选择性质是指问题的全局最优解可以通过局部最优解来得到；最优子结构是指问题的最优解包含其子问题的最优解。

---

还有和上面一题相似的活动安排问题也是贪心的经典题，但我暂时找不到合适的题目出处，就用【算法设计与分析】活动安排问题（动态规划和贪心算法）_活动安排 动态规划-CSDN博客这篇博客的截图了（正常应该会要我们自己排序）

问题描述：给定n个活动活动，每个活动都有一个开始时间和结束时间。目标是在一个空间内安排尽可能多的活动。

思路：将活动按结束时间从小到大排序，每次选择结束时间最早且与已安排的活动不冲突的活动（关键）

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(pair<int,int>a,pair<int,int>b){return a.second<b.second;
}
int main(){int n,i,start,end;cin>>n;vector<pair<int,int> >events;for(i=0;i<n;i++){cin>>start>>end;events.push_back({start,end});}sort(events.begin(),events.end(),cmp);int count=0,endt=0;for(auto event:events){      //基于范围的for循环，event遍历events容器中的每个元素（C++11及以后的保准）if(event.first>=endt){   //与已安排活动不冲突count++;endt=event.second;}}cout<<count;return 0;
}

本篇我的第11行代码蓝色dev-c++是运行不了的，在文末我会推荐一款"新的"傻瓜集成开发环境。

 题目：排座椅  NC16618

 这怎么贪呢?有点想不出啊

思路：要使答案最优，就要让K条横线和L条竖线穿过尽可能多的会交头接耳的两个人。所以分别记录每行每列所能分割的学生对数，再从大到小排序即可。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
struct jl{int index,num;
}row[1010],col[1010];    //row[index]存储index行能分割的学生对数
bool cmp1(jl a,jl b){return a.num>b.num;  //按分割数从大到小排
}
bool cmp2(jl a,jl b){return a.index<b.index;
}
int main(){int m,n,k,l,d;cin>>m>>n>>k>>l>>d;int x,y,p,q,i;for(i=0;i<d;i++){cin>>x>>y>>p>>q;if(x==p){        //行号相等，列计数+1y=min(y,q);col[y].index=y;col[y].num++;}else if(y==q){x=min(x,p);row[x].index=x;row[x].num++;}}sort(row,row+m+1,cmp1);sort(col,col+n+1,cmp1);sort(row,row+k,cmp2);        //再将k行按序号从小到大输出sort(col,col+l,cmp2);for(i=0;i<k;i++) cout<<row[i].index<<" ";cout<<endl;for(i=0;i<l;i++) cout<<col[i].index<<" ";return 0;
}

题目：矩阵消除游戏  NC200190

这题就有些复杂了，选的行会影响到剩下列和的值，只考虑选每一次的最优解，会影响到下一次的选择吧！我不是球球，帮不了呀。看了大佬的题解，我佬果然还是我佬

思路过程： 如果只按行选，或者只按列选，直接贪心就可以了。但没有交叉（只选行或只选列）只能保证选的数字最多，未必的最大的，例如：3  3  2   【【1  5  1】【5 5 5】【1 5 1】】。每次选最优解也不一定最大，例如：4 4 3【【 1 1 9 3】【 1 8 10 8】【1 2 7 2】【 1 2 2 2】】，先选第三列，然后选第二行和第四列，但是直接选选第二三四列结果更大。有点上一篇背包的意思，给你一个体积为V的背包，再给你若干件体积不同的物品，希望选一些物品尽量装满，你会上来就选择最大的吗？     

思路：   n，m都小于15，说明本题可以暴力枚举 。我们采用先枚举后贪心的方法， 先枚举所有行的情况（二进制枚举法），再贪心选择最多的前几列

二进制枚举——当每个个体都面对两种选择的时候，可以用一个01串表示，对于本题，每一行有选和不选两种可能，假设有5行的话，我们就可以用一个长度为5的01串来表示，0表示不选，1表示选，如：01001 表明选第2和第5行。二进制1的数量就是选取行的数量，二进制1的位置就是选取行的位置。长度为n的01串的十进制范围在0~2^n-1

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k;
int a[20][20];
long long row[20],col[20];  //row[i]存储第i行数据的和
int flag[20];                   //标记所选行
int count(int x){int c=0;for(int i=0;i<n;i++){if(x&(1<<i)){           //位运算在A+B problem那一篇有介绍,大家也回顾一下flag[i+1]=1;        //当然也可以直接二进制转换c++;}else{flag[i+1]=0;}}return c;
}
bool cmp(long long a,long long b){return a>b;
}
int main(){int i,j;long long sum=0;           //该养成long long潜意识了cin>>n>>m>>k;for(i=1;i<=n;i++){for(j=1;j<=m;j++){cin>>a[i][j];row[i]+=a[i][j];sum+=a[i][j];}}if(k>=n||k>=m){          //k>=行或列，则可以选择全部cout<<sum;return 0;}sum=0;for(i=0;i<(1<<n);i++){   //遍历2^n种行选择情况long long ans=0;        //存储该种情况的最大分数int numh=count(i);      //该情况所选行数int numl=k-numh;if(numl>m||numl<0){     //这种情况不存在continue;     } for(j=1;j<=n;j++){if(flag[j]){ans+=row[j];}}memset(col,0,sizeof(col));for(j=1;j<=m;j++){      //计算选完行后的列和for(int h=1;h<=n;h++){if(!flag[h]){col[j]+=a[h][j];}}}sort(col+1,col+m+1,cmp);  for(j=1;j<=numl;j++){            ans+=col[j];  //从最后面(最大)开始加}sum=max(sum,ans);}cout<<sum;return 0;
}

下一题是一道提高组的题，本来觉得不好想，不分享算了。但它由特殊到一般推公式的思想还挺牛波一的，还是简单分析下思路，代码就贴我以前写的了

题目：国王的游戏  NC16561

思路： 以下图片截自一位牛客博主savage，据图，所以我们只需将ai​×bi从小到大排序，便能获得最多大臣的最小值。最后注意数据大小，利用之前学的高精度

 代码：

#include<iostream>
using namespace std;
string cheng(string a,string b){int lena=a.size(),lenb=b.size(),lenc=lena+lenb;string c(lenc,'0');int i,j;for(i=lena-1;i>=0;i--){for(j=lenb-1;j>=0;j--){int x=a[i]-'0',y=b[j]-'0';int num=x*y+c[i+j+1]-'0';c[i+j+1]=num%10+'0';c[i+j]+=num/10;}}c.erase(0,c.find_first_not_of('0'));return c;
}
void chu(string s,int b){int a[1000000],ans[100000];int len=s.size(),i,res=0;for(i=0;i<len;i++){a[i]=s[i]-'0';}for(i=0;i<len;i++){res=res*10+a[i];ans[i]=res/b;res%=b;}i=0;while(ans[i]==0){i++;}for(int j=i;j<len;j++){cout<<ans[j];}
}
int main(){int n,a,b,mx=0;cin>>n>>a>>b;string c=to_string(a);while(n--){cin>>a>>b;c=cheng(c,to_string(a));mx=max(mx,a*b);} chu(c,mx); return 0;
}