学习《挑战程序设计竞赛》
2.2贪心算法
硬币问题
有1元、5元、10元、50元、100元、500元的硬币各C1 C5 C10 C50 C100 C500 。现在要用这些硬币来支付A元,最少需要多少枚硬币?
#includeusing namespace std; const int v[6]={1,5,10,50,100,500}; int C[6]; int A; void solve() { int ans=0; for(int i=5;i>=0;i--) { int t=min(A/v[i],C[i]); A-=t*v[i]; ans+=t; if(t!=0) { cout<<"需要面值为"< C[i]; } cin>>A; solve(); }
区间调度问题
有n项工作,每项工作分别在si开始,ti结束。对每项工作,你都可以选择参加或不参加,但选择了参加某项工作就必须至始至终参加全程参与,即参与工作的时间段不能有重叠(即使开始的时间和结束的时间重叠都不行)。
按书上讲述的,选择算法一:每次都选取结束时间最早的工作
#include#include #define MAX 10000 using namespace std; int N,S[MAX],T[MAX]; pair p[MAX]; void solve() { for(int i=0;i N; for(int i=0;i >S[i]; } for(int i=0;i >T[i]; } solve(); }
字典序最小问题
给定长度为N的字符串S,要构造一个长度为N字符串T。T是一个空串,反复执行下列任意 *** 作:
l 从S的头部删除一个字符,加到T的尾部;
l 从S的尾部删除一个字符,加到T的尾部;
目标是要构造字典序尽可能小的字符串T。
可知算法为每次选择较小的字母放在新构成的串中,这里使用STL中deque来实现更加方便
#include#include #define MAX 10000 using namespace std; int N=0; deque S,T; char temp; void solve() { char p,q; while(S.size()) { p=S.front(); q=S.back(); if(p >N; for(int i=0;i>temp; S.push_back(temp); } solve(); return 0; }
Saruman’s Army
#include#include #include #define MAX 10000 using namespace std; int N=0,R=0; int X[MAX]; void solve() { sort(X,X+N); int i=0,ans=0; while(i N>>R; for(int i=0;i >X[i]; } solve(); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)