admin 管理员组文章数量: 887021
贪心
贪心----硬币、区间、字典序问题
- 硬币问题
- 区间问题
- 字典序问题
贪心法就是遵循某种规则，不断贪心的选取当前最优策略的算法设计方法
硬币问题
题意：
有1元，5元，10元，50元，100元，500元的硬币各C1 , C5 , C10 , C50 , C100 , C500 枚。现在要用这些硬币来支付A 元，最少需要多少枚硬币？假设本题至少存在一种支付方案。
限制条件：
0<=C1 , C5 , C10 , C50 , C100 , C500<=100000000000
0<=A<=1000000000000
样例：
输入
C1=3,C5=2,C10=1,C50=3,C100=0,C500=2,A=620;
输出
6（500元硬币1枚，50元2枚，10元1枚，5元2枚，合计6枚）
思路：
优先使用面值最大的硬币
代码：
#include"bits/stdc++.h"
using namespace std;int main(){int v[6]={1,5,10,50,100,500};//输入硬币面值 int c[6]={3,2,1,3,0,2};//输入硬币个数 int a=620; //输入所求面值大小 int ans=0;for(int i=5;i>=0;i--){int t=min(a/v[i],c[i]);//比较最大使用最大值面额个数和实际最大面额存在个数 a-=t*v[i];//求除去使用后最大面额值剩余多少 ans+=t;//相加求所需硬币个数 }printf("%d\n",ans);
}
区间问题
题意：
有n项工作，每项工作在si开始，ti结束。对于每项工作，你可以选择参与与否，但是参与工作的时间段不能重复，那么最多参与几项工作？
限制条件：
1<=N<=100000
1<=si<=ti<=1e9
输入
n=5,s={1,2,4,6,8} t={3,5,7,9,10}
输出
3（选取工作135）
思路：
- 选取结束时间最早工作
- 选用时最短工作
- 每次选取的与最早工作有重叠的工作
代码：
#include"bits/stdc++.h"
using namespace std;
//区间问题
const int MAX_N=100000;
//对输入数据进行初始化 int n=5,s[MAX_N]={1,2,4,6,8},t[MAX_N]={3,5,7,9,10};//用于工作排序的pair数组 pair<int,int> itv[MAX_N];int main(){//把s,t存入pair,分别为first和secondfor(int i=0;i<n;i++){itv[i].first=t[i];itv[i].second=s[i];} //对pair数组从大到小排序 sort(itv,itv+n);int ans=0,h=0;for(int i=0;i<n;i++){if(h<itv[i].second){//寻找工作开始的时间大于工作结束的时间 ans++; //计数 h=itv[i].first;//更新t的值 }}cout<<ans<<endl;
}
字典序问题
题目大意：
给你一个长为N的字符串S，并提供下列2种操作
- 把S的第一个字母添加到字符串T的末尾，并从S中删除
- 把S的最后一个字母添加到字符串T的末尾，并从S中删除
让你构造出字典序最小的字符串T
思路：
我们比较S和将S反转后的S’的字典序大小
- S < S’我们选择首字母
- S > S’我们选择尾字母
输入：
n=6
a=’‘ACDBCD’’
输出：
“ABCBCD”
代码：
//字典序最小问题
#include"bits/stdc++.h"
using namespace std;int main(){//输入 int n;cin>>n; //例n=6 char a[n];//输入字符串 例如a[6]={'A','C','D','B','C','D'} for(int i=0;i<n;i++){cin>>a[i];}//设置字符串开头结尾的标志 int b=0,c=n-1;while(b<=c){bool left=false;for(int i=0;i<n;i++){if(a[b+i]<a[c-i]){//如果开头字母字典序小于末尾字母字典序 left=true;break;}else if(a[b+i]>a[c-i]){left=false;break;}}if(left){putchar(a[b++]);//输出开头删除的字母 }else{putchar(a[c--]);//输出末尾删除的字母 } }putchar('\n');return 0;
}
本文标签： 贪心
版权声明：本文标题：贪心 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/free/1700374211h419214.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论