贪心刷题~
1、洛谷P2240 【深基12.例1】部分背包问题
贪心策略：拿金币单价高的。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct gold{
int v;
int m;
} q[101];
bool cmp(gold a,gold b){
return a.v*b.m>b.v*a.m; //按金币单价大的排：a.v/a.m > b.v/b.m
}
int main()
{
int n,T;
cin>>n>>T;
for(int i=0;i<n;i++)
cin>>q[i].m>>q[i].v;
sort(q,q+n,cmp);
double va=0;
int ma=T;
for(int i=0;i<n;i++)
if(q[i].m<=ma){ //能把这一价格的全拿完
va+=q[i].v;
ma-=q[i].m;
}
else{
va+=1.0*q[i].v/q[i].m*ma; //要*1.0转化为浮点数类型！！
break; //到这一步 说明ma=0，直接退出
}
printf("%.2lf",va);
return 0;
}
2、洛谷P1208 [USACO1.3]混合牛奶 Mixing Milk
和上一题基本相同。。
贪心策略：拿牛奶单价低的。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct milk{
int vv;
int mm;
}q[50010];
bool cmp(milk a,milk b){
return a.vv<b.vv;
}
int main()
{
int n,m; //n,m不要弄混了...
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>q[i].vv>>q[i].mm;
sort(q,q+m,cmp);
int va=0,ma=n;
for(int i=0;i<m;i++)
if(q[i].mm<=ma){
va+=q[i].vv*q[i].mm;
ma-=q[i].mm;
}
else{
va+=q[i].vv*ma;
break;
}
cout<<va;
return 0;
}
3、洛谷P1478 陶陶摘苹果（升级版）
又一道大差不差。。
贪心策略：摘耗力小的，当然前提是要能摘到。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct apple{
int h;
int c;
} q[50010];
bool cmp(apple a,apple b){
return a.c<b.c;
}
int main()
{
int n,s,a,b;
cin>>n>>s>>a>>b;
for(int i=0;i<n;i++)
cin>>q[i].h>>q[i].c;
sort(q,q+n,cmp);
int ans=0,rem=s;
for(int i=0;i<n;i++)
if(q[i].h<=a+b){
rem-=q[i].c;
if(rem<0) //没有 = 哦
break;
else
ans++;
}
cout<<ans;
return 0;
}4、洛谷P1223 排队接水
经典的数学排队洗澡问题。。
贪心策略： 排用时少的。
用时越少的排越前面，没接水的等的时间就越少，平均等待时间就越少。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct peo{
int t;
int num;
} q[1010];
bool cmp(peo a,peo b){
return a.t<b.t;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>q[i].t;
q[i].num=i;
}
sort(q+1,q+n+1,cmp);
double sum=0;
for(int i=1;i<=n;i++){
cout<<q[i].num<<" ";
sum+=q[i].t*(n-i);//等待总时间 = q[1].t*(n-1) + q[2].t*(n-2) +...+q[n-1].t*1
}
printf("\n%.2lf",sum/n);
return 0;
}5、洛谷P1094 [NOIP2007 普及组] 纪念品分组
每组最多两件，专门为双指针而出的呀！
贪心策略：价格最低最高的礼品分一组，当然前提是满足条件；不满足则价格高的为一组，这样价格低的更可能和其他价格高的分一组，使组数最小。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int w,n,q[30010];
cin>>w>>n;
for(int i=0;i<n;i++)
cin>>q[i];
sort(q,q+n);
int ans=0;
int l=0,r=n-1;
while(l<=r){
if(q[l]+q[r]<=w){
l++;
r--;
}
else
r--;
ans++;
}
cout<<ans;
return 0;
}
6、洛谷P4995 跳跳！
贪心策略：在最高和最低的石头间来回横跳。
还是双指针。。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int n,h[310]={0};
cin>>n;
for(int i=1;i<=n;i++)
cin>>h[i];
sort(h+1,h+n+1);
long long ans=0; //要开long long,最大约为(10^4*10^4) * 300 > 10^9
int l=0,r=n; //模拟跳跃过程
while(l<r){
ans+=(h[r]-h[l])*(h[r]-h[l]);
l++;
ans+=(h[l]-h[r])*(h[l]-h[r]);
r--;
}
cout<<ans;
return 0;
}7、洛谷P1803 凌乱的yyy / 线段覆盖
贪心策略：先参加结束时间早的比赛，当然前提是这场比赛 开始时间晚于前一场比赛。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct game{
int s;
int e;
} q[1000010];
bool cmp(game a,game b){
return a.e<b.e;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>q[i].s>>q[i].e;
sort(q,q+n,cmp);
int ans=0;
int last=0; //记录上一场的结束时间
for(int i=0;i<n;i++)
if(last<=q[i].s){
ans++;
last=q[i].e;
}
cout<<ans;
return 0;
}
9、洛谷P5019 [NOIP2018 提高组] 铺设道路
贪心策略：若该坑深度大于前一坑，则填其深度之差。
证明：
假设现在有一个坑，但旁边又有一个坑。
你肯定会选择把两个同时减1；
那么小的坑肯定会被大的坑“带着”填掉。
大的坑也会减少a[i]-a[i-1]的深度，可以说是“免费的”；
所以这样贪心是对的。
这是一个局部策略，能使当前答案最优（比如样例里的第一个深度4，由于4比前一深度0大，所以ans要加(4-0)，这放在整体上来看显然不对(2、3<4)，但对于第一个深度4和其前一深度0 来说就是最优的），不能放在整体上来看。
但当所有局部最优时，这题整体就有最优（贪心嘛，废话。。）。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int n,d[100010]={0};
cin>>n;
for(int i=1;i<=n;i++)
cin>>d[i];
int ans=0;
for(int i=1;i<=n;i++)
if(d[i]>d[i-1])
ans+=d[i]-d[i-1];
cout<<ans;
return 0;
}不会贪心的话用递归也行（更直观）：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int n,a[100010],f[100010]; //f表示最少天数
cin>>n;
for(int i=1;i<=n;i++)
cin>>d[i];
f[1]=d[1];
for(int i=2;i<=n;i++)
{
if(d[i]<=d[i-1]) //d[i]<=d[i-1]时，
f[i]=f[i-1]; //填d[i-1]时顺便填上d[i]
else //不然的话，
f[i]=f[i-1]+(d[i]-d[i-1]);//还要填上剩余的坑
}
cout<<f[n];
return 0;
}10、洛谷P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
贪心策略：每次合并较小的堆。
合并后要将新的堆继续进行排序，用sort会TLE，
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int n,q[10010];
cin>>n;
for(int i=0;i<n;i++)
cin>>q[i];
sort(q,q+n);
int ans=0;
int i=0;//合并次数
while(i<n-1)
if(q[i]){
q[i]+=q[i+1];
ans+=q[i];
q[i+1]=0;
sort(q,q+n);
i++;
}
cout<<ans;
return 0;
}但可以用STL里的优先队列priority_queue，
这样每次操作后都会自动帮你排序（也可以手写堆但我不会。。）。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue> //要引入这个头文件！
using namespace std;
int n,x,ans;
priority_queue< int,vector<int>,greater<int> >q;//greater:由小到大排列
//less:由大到小排列
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
q.push(x);
}
while(q.size()>=2){//因为每次a,b的和都会入队，所以最后一次操作后size=1，退出循环
int a=q.top(); q.pop();//得到最小的两个数，
int b=q.top(); q.pop();//并将其弹出队列
ans+=a+b;
q.push(a+b);//将其和入队
}
cout<<ans;
return 0;
}11、洛谷P3817 小A的糖果
先从第一个糖果盒和第二个开始； 如果一个糖果盒的数量就超限了，我们当然至少要把它吃到剩下x个； 然后如果单论两个都没有超限，但加起来超限了怎么办呢？
首先第一个糖果盒是只有一个分组的（和第二个）， 而第二个糖果盒却有两个分组（和第1个/和第3个）； 所以如果我们吃掉第一个里的，只会减少一个分组的量，而如果吃掉第二个里的，可以减少2个分组的量。所以我们要尽量吃掉第二个（”中间的”）里的糖果。
处理好第一个分组后，来看第二个，因为第一个分组已经被处理好了，所以可以无视它，然后问题又变成了前一个问题。 以此类推就好了。
如果不单独考虑第一个的话，因为是优先吃第二个，所以若第一个特别大，那么要使其和小于x，第二个可能会被吃到负数。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,x,q[100010];
int main()
{
cin>>n>>x;
long long ans=0;
int eat;
for(int i=1;i<=n;i++){ //q[0]=0,相当于单独考虑了第一个糖果盒
cin>>q[i];
if(q[i]+q[i-1]>x){
eat=q[i]+q[i-1]-x;
ans+=eat;
q[i]-=eat; //优先吃“中间的”，影响最大，最贪心
}
}
cout<<ans;
return 0;
}
12、洛谷P1106 删数问题
首先来看一个例子-> 输入N和4
- N=175438 //删掉7
- 15438 //删掉5
- 1438 //删掉4
- 138 //删掉8
- 13 //解为13
贪心策略：寻找高位上的减区间，将减区间的第一个数删去（这样最贪），直到删了s个数，最后输出。但是注意一点，就是要删去前导0。
//一些数据：
// 输入 输出
//133420 3 120
//1444 3 1
//20018 2 1
//10000 1 0#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
string N;
int s;
cin>>N>>s;
int len=N.size();
while(s--){
for(int i=0;i<len;i++)
if(N[i]>N[i+1]){
for(int j=i;j<len-1;j++) //将要删去的数用后面的数覆盖掉
N[j]=N[j+1];
break; //删掉一位后立即重新开始删除
}
len--; //别忘了！不然会多输出
}
int i=0; //去除前导零：
while(i<len && N[i]=='0') i++;
if(i==len)
cout<<0;
else
for(i;i<len;i++)
cout<<N[i];
return 0;
}//当时10、11、12题我认为我是不会写的，但搞懂后感觉还是能做。所以还是要多尝试，多努力吧