2021-10-17

学习《挑战程序设计竞赛》
2.2贪心算法
硬币问题
有1元、5元、10元、50元、100元、500元的硬币各C1 C5 C10 C50 C100 C500 。现在要用这些硬币来支付A元，最少需要多少枚硬币？

#include
using 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;
}