《算法笔记》4.4小节——算法初步->贪心
2020-04-08 本文已影响0人
木子李_0961
@[TOC]
Contest100000584 - 《算法笔记》4.4小节——算法初步->贪心
4.4小节——算法初步->贪心
讲解和例题
4.4.1 简单贪心
在这里插入图片描述
例题 PAT B1020 月饼
1020 月饼
来自 https://pintia.cn/problem-sets/994805260223102976/problems/type/7
在这里插入图片描述
在这里插入图片描述
//PAT B1020 月饼
//2143 Problem F 迷瘴
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)//按照从小到大排列
{
return a<b;
}
int main()
{
int C;
while(cin>>C)
{
while(C--)
{//n种浓度的万能药水，体积V都相同,浓度不大于 W%
int n,V,W;
cin>>n>>V>>W;
int P[n]={0};
for(int i=0;i<n;i++)//表示n种药水的浓度Pi%
{
cin>>P[i];
}
sort(P,P+n,cmp);
int res_V=V; double res_P=P[0];
if(P[0]>W)//最低浓度不满足，则无法配置合格药水
{
res_V=0;res_P=0.00;
}
else
{
for(int i=1;i<n;i++)
{
if((res_P*res_V+P[i]*V)/(res_V+V) <= W)//若预加入下一瓶药仍按满足，则混合下一瓶药
{
res_P = (res_P*res_V+P[i]*V)/(res_V+V);
res_V += V;
}
else break;
}
}
printf("%d %.2f\n",res_V,res_P/100);
}
}
return 0;
}
例题2 PAT B1023组个最小数
1023 组个最小数
来自 https://pintia.cn/problem-sets/994805260223102976/problems/type/7
在这里插入图片描述
//PAT B1023 组个最小数
//PAT B1023 组个最小数
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int cnt[10];//记录数字0~9的个数
for(int i=0;i<10;i++)
{
scanf("%d",&cnt[i]);
}
for(int i=1;i<10;i++)//从1~9中选择cnt不为0的最小的数字
{
if(cnt[i]>0)
{
printf("%d",i);
cnt[i]--;
break;//找到一个之后就中断
}
}
for(int i=0;i<10;i++)//从0~9输出对应个数的数字
{
for(int j=0;j<cnt[i];j++)
{
printf("%d",i);
}
}
return 0;
}
4.4.2 区间贪心
区间不相交问题：给出N个开区间(x,y)，从中选择尽可能多的开区间，使得这些区间两两没有交集。
在这里插入图片描述
//4.4.2区间贪心区间不相交问题
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 110;
struct Inteval
{
int x,y;//开区间左右端点
}I[maxn];
bool cmp(Inteval a,Inteval b)
{
if(a.x != b.x) return a.x>b.x;//先按左端点从大到小排序
else return a.y<b.y;//左端点相同的按右端点从小到大排序
}
int main()
{
int n;
while(scanf("%d",&n),n!=0)//什么骚操作？？
{
for(int i=0;i<n;i++)
{
scanf("%d%d",&I[i].x,&I[i].y);
}
sort(I,I+n,cmp);//把区间排序
//ans记录不相交区间个数，lastX记录上一个被选中区间的左端点
int ans=1,lastX=I[0].x;
for(int i=1;i<n;i++)
{
if(I[i].y <= lastX)//如果该区间右端点在lastX左边
{
lastX = I[i].x;//以I[i]作为新选中的区间
ans++;//记录不想交区间个数
}
}
printf("%d\n",ans);
}
return 0;
}
Codeup习题
1126-ProblemA-看电视
来自 http://codeup.cn/contest.php?cid=100000584
题析：参考不相交区间问题，几乎一样
//1126ProblemA看电视
//参考不相交区间问题，几乎一样
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct program//节目结构体
{
int s;//节目开始时间
int e;//节目结束时间
}pro[105];
bool cmp(program a,program b)//比较规则
{
if(a.s!=b.s) return a.s>b.s;//先按照节目开始时间从大到小排序
else return a.e<b.e;//开始时间相同的按照结束时间从小到大排序
}
int main()
{
int n;
while(scanf("%d",&n) != EOF && n!=0)
{
for(int i=0;i<n;i++)
{
scanf("%d%d",&pro[i].s,&pro[i].e);//输入各个节目开始结束信息
}
sort(pro,pro+n,cmp);//节目排序
//ans记录不冲突节目个数，lastX记录上一个被选中节目区间的开始时间
int ans=1,lastS=pro[0].s;//从一个时间段开始计数，所以初始值为1
for(int i=0;i<n;i++)
{
if(pro[i].e <= lastS)//如果该节目结束时间在lastS左边
{//更新上一个时间段的开始时间
lastS = pro[i].s;//以pro[i]作为新选中的节目段
ans++;//记录不冲突节目个数
}
}
printf("%d\n",ans);
}
return 0;
}
1128-ProblemB-出租车费
来自 http://codeup.cn/contest.php?cid=100000584
题析：
要找到分段与不分段的交界点在
大佬讲解的很详细：
https://blog.csdn.net/qian2213762498/article/details/81807247
自己总结：
在这里插入图片描述
//1128ProblemB出租车费
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
if(n==0)
break;
double money=0;
if(n<=4)//第一段
{
money = 10;
}
else if(n>4 && n<=8)//第二段
{
money = 10+(n-4)*2;
}
else//第三段需要考虑是否分段
{
while(n>=8)//先变量代换，这里还用n
//特别注意此处的循环
{
money+=18;
n-=8;
}
if(n<=4)//不分段，继续分段函数三
{
money+=2.4*n;
}
else//分段，到分段函数二
{
money+=10+(n-4)*2;
}
}
// cout<<money<<endl;
int temp = (int)money;//最终花费整数部分
if((money-temp)==0)
// printf("%d\n",money);//之前money没转换为int型，一直报错
printf("%d\n",(int)money);
else
printf("%.1f\n",money);
}
return 0;
}
2031-ProblemC-To Fill or Not to Fill
来自 http://codeup.cn/contest.php?cid=100000584
题析：
//2031 Problem C To Fill or Not to Fill
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct station
{
double price;
double distance;
}st[1010];
bool cmp(struct station a,struct station b)
{
return a.distance < b.distance;
}
int main()
{
double Cmax,dis,Davg;
int N;
scanf("%lf%lf%lf%d",&Cmax,&dis,&Davg,&N);
double maxdis = Cmax * Davg;//油箱满油最多能走的距离
for(int i=0;i<N;i++)
{
scanf("%lf%lf",&st[i].price,&st[i].distance);
}
sort(st,st+N,cmp);//按照到起点（杭州）距离来排序加油站
st[N].distance = dis;//终点到杭州的距离为d
st[N].price = 0;//终点不需要加油
if(st[0].distance != 0)//起点没有油则无法开启行程
{
printf("The maximum travel distance = 0.00\n");
}
else
{
int cur_station = 0;//当前加油站编号
double sumprice = 0,cur_oil = 0;
while(cur_station < N)
{
int k = -1;//初始化油价最低的站号
double priceMin = 999999999;
for(int i = cur_station+1;i<=N && (st[i].distance - st[cur_station].distance) <= maxdis;i++)
//循环遍历加油站路径找寻耗油量最小值的站，满足耗油量小于maxDis
{
if(st[i].price < priceMin)//priceMin记录最低油价
{
priceMin = st[i].price;
k = i;
if(st[cur_station].price > priceMin)//若找寻加油站价格比当前还低，则直接开车去，循环中断
{
break;
}
}
}
if(k == -1) break;//未经过遍历循环，则无法到达下一站，直接输出最大花费即可
double need = (st[k].distance - st[cur_station].distance)/Davg;//计算从当前站到k站所需油量
//**如果当前站的油价比k站的高,我们就加正好到k站的油量need
if(priceMin < st[cur_station].price)
{
if(cur_oil < need)//当前油无法到达k，则加到刚好够
{
sumprice += (need - cur_oil)* st[cur_station].price;
cur_oil = 0;//到k剩油
}
else//若足够，到k油量即为原本油量减去到k所耗费的油
{
cur_oil -= need;
}
}
//**否则当前站油价较低，则在当前站加满油
else
{
sumprice += (Cmax - cur_oil) * st[cur_station].price;
cur_oil = Cmax - need;//到k剩油
}
cur_station = k;
}
if(cur_station == N)
{
printf("%.2f\n",sumprice);
}
else
{
printf("The maximum travel distance = %.2f\n",maxdis + st[cur_station].distance);
}
}
return 0;
}
参考链接：https://blog.csdn.net/ActionBeam/article/details/88411842
2132-ProblemD-Repair the Wall
来自 http://codeup.cn/contest.php?cid=100000584
题析：
//2132 ProblemD Repair the Wall
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int block[605]={0};
int l,n,need,i;
while(scanf("%d%d",&l,&n) != EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",&block[i]);
}
sort(block,block+n,cmp);//将填充块从大到小排列
need=l;
for(i=0;i<n;i++)//裂缝所需减去填充块
{
need -= block[i];
if(need<=0) break;
}
if(need>0)//若need仍大于0，说明填充块不够
{
printf("impossible\n");
}
else
{
printf("%d\n",i+1);
}
}
return 0;
}
2134-ProblemE-FatMouse's Trade
来自 http://codeup.cn/contest.php?cid=100000584
题析：
//2134 Problem E FatMouse's Trade
//2134 Problem E FatMouse's Trade
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct room_i
{
double J;//J[i]javaBean
double F;//需要F[i]猫粮
};
bool cmp(room_i a,room_i b)//按照需要猫粮与获得豆子比值从小到大排列
{
return (a.F/a.J)<(b.F/b.J);
}
int main()
{
int M,N;
while(cin>>M>>N&&M!=-1&&N!=-1)
{
struct room_i room[N];
for(int i=0;i<N;i++)
{
cin>>room[i].J>>room[i].F;
}
sort(room,room+N,cmp);
double res=0.00;
for(int i=0;i<N;i++)
{
if(M>room[i].F)//如果猫粮满足守卫需求，则拿到所有豆子
{
res += room[i].J;
M -= room[i].F;
}
else//若不满足守卫要求，按照比例拿豆子，并退出循环
{
res += room[i].J*(M/room[i].F);
break;
}
}
printf("%.3f\n",res);
}
return 0;
}
2143-ProblemF-迷瘴
来自 http://codeup.cn/contest.php?cid=100000584
题析：
//2143 Problem F 迷瘴
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)//按照从小到大排列
{
return a<b;
}
int main()
{
int C;
while(cin>>C)
{
while(C--)
{//n种浓度的万能药水，体积V都相同,浓度不大于 W%
int n,V,W;
cin>>n>>V>>W;
int P[n]={0};
for(int i=0;i<n;i++)//表示n种药水的浓度Pi%
{
cin>>P[i];
}
sort(P,P+n,cmp);
int res_V=V; double res_P=P[0];
if(P[0]>W)//最低浓度不满足，则无法配置合格药水
{
res_V=0;res_P=0.00;
}
else
{
for(int i=1;i<n;i++)
{
if((res_P*res_V+P[i]*V)/(res_V+V) <= W)//若预加入下一瓶药仍按满足，则混合下一瓶药
{
res_P = (res_P*res_V+P[i]*V)/(res_V+V);
res_V += V;
}
else break;
}
}
printf("%d %.2f\n",res_V,res_P/100);
}
}
return 0;
}
5038-ProblemG-找零钱
来自 http://codeup.cn/contest.php?cid=100000584
题析：
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int money[5]={50,20,10,5,1};//从大面值往小面值分配
int main()
{
int n,x;
while(scanf("%d",&n) != EOF)
{
for(int i=0;i<5;i++)
{
x=n/money[i];//x为每个面值对应的数量
if(x)
{
printf("%d*%d",money[i],x);//每种面值钞票及其数量输出
n=n%money[i];//余额，下一面值分配用
if(n)//未分配完，需要连接下一面额的“+”
{
printf("+");
}
}
}
printf("\n");
}
return 0;
}
