一、 经典贪心问题介绍（事件序列问题等）
- 硕鼠的交易（ FatMouse’ Trade) HDOJ 1009 `
解题思路：贪心思路要换取的咖啡豆最多，就要考虑性价比的高低，将N个房间定义为一个结构体数组，利用sort函数按照性价比从高到低排序，依次购买，直至M=0。
#include<bits/stdc++.h>
using namespace std;
struct mouse{
double j; //咖啡豆
double f; //猫粮
double rate;
}JavaBean[1005]; //结构体
bool cmp(mouse a,mouse b){
return a.rate>b.rate;
} //排序规则
int main()
{
while(1){
int M,N;
double res=0; //最终用M猫粮可以换取的咖啡豆数量
cin>>M>>N;
if(M==-1&&N==-1)
break; //输入循环终止条件
for(int i=0;i<N;i++){
cin>>JavaBean[i].j>>JavaBean[i].f ;
JavaBean[i].rate =JavaBean[i].j /JavaBean[i].f ;
} //处理结构体数组里的数据
sort(JavaBean,JavaBean+N,cmp); //调用sort函数对结构体数组排序
for(int i=0;i<N;i++){
if(M>=JavaBean[i].f ){ //当现有的猫粮大于该组的猫粮数
res+=JavaBean[i].j;
M-=JavaBean[i].f;
}
else{ //现有的猫粮不足以全部换取改组的猫粮数
res=JavaBean[i].rate*M+res;
break;
}
}
printf("%.3f\n",res);
}
return 0;
}
- 田忌赛马(Tian Ji – The Horse Racing) HDOJ 1052
解题思路：
贪心思路：先用田忌最快的马与国王最快的马比较：
1当田忌最快的马比国王最快的马快，则直接VS，res++;
2当田忌最快的马不比国王最快的马快时：
2.1若田忌最慢的马比国王最慢的马快，则直接VS ,res++;
2.2否则用田忌最慢的马与国王最快的马比，慢了, res–；相等，res不变。（田忌最慢的马已经无法赢得任意一场比赛，若想要输的价值最大，就与国王最快的马VS)
（总共比赛次数为每人拥有的马匹数，平局的时候，本场res（输赢次数）不加不减）
#include<bits/stdc++.h>
using namespace std;
int m[1001],n[1001];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
while(1){
int T,res=0; //res是输赢的次数
cin>>T;
if(T==0)
break; //多组数据输入的循环终止条件
for(int i=0;i<T;i++)
cin>>m[i];
for(int i=0;i<T;i++)
cin>>n[i];
sort(m,m+T,cmp);
sort(n,n+T,cmp); //将马的速度从大到小排序
int mfirst=0,nfirst=0,mlow=T-1,nlow=T-1;
while(T--){ 每组有T匹马，则总共赛T场
if(m[mfirst]>n[nfirst]) //m组最快的马比n组最快的马快
{
res++; //赢一场
mfirst++;
nfirst++; //将比赛完的马剔除序列
}
else //m组最快的马不快与n组最快的马
{
if(m[mlow]>n[nlow]) //m组最慢的马比n组最慢的快
{
res++; //赢一场
mlow--;
nlow--; //将比赛完的马剔除序列
}
else if(m[mlow]<n[nfirst]) //如果m组最慢的马比n组最慢的慢，则m组最慢的马VS n组最快的马
{
res--; //输一场
mlow--;
nfirst++; //将比赛完的马剔除序列
}
}
}
cout<<res*200<<endl;
}
return 0;
}
- 经典贪心事件序列问题 例：今年暑假不AC HDOJ 2037
解题思路：将N组数据的结束时间利用sort函数按照从小到大的顺序排序，优先选择在不影响前面已选择活动的同时结束时间最早的活动。
#include<bits/stdc++.h>
using namespace std;
struct perform{
int T1; //活动开始时间
int T2; //活动结束时间
}P[101];
bool cmp(perform a,perform b)
{
return a.T2<b.T2; //将结构体数组按照结束时间从小到大排序
}
int main()
{
while(1){
int n,res=1;
cin>>n;
if(n==0)
break; //输入数据循环终止的条件
for(int i=0;i<n;i++){
cin>>P[i].T1>>P[i].T2;
}
sort(P,P+n,cmp); //调用sort函数排序
int m=0; //当前最新选择的活动序号
for(int i=1;i<n;i++){
if(P[i].T1>=P[m].T2){ //将要选择的活动开始时间与上一个已选择的活动结束时间比较，检查是否对之前的活动有影响
res++;
m=i; //如果没有影响，选择的活动数量res+1，m调整
}
}
cout<<res<<endl;
}
return 0;
}
- Moving Tables HDOJ 1050
解题思路：将搬桌子时房间被经过的次数看做数组元素初始为0，走廊两侧的房间看做数组元素的同一个地址，类似于桶排序，N组桌子在搬的过程中对应的数组元素+1，最后数组元素（某个房间被经过次数）的最大值也就是最多使用走廊的次数。
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--) { //总组数循环
int N;
cin>>N; //每组搬桌子次数
int p[200]={0}; //在每组循环开始，将搬桌子时经过的房间次数当做数组元素，初始为0
while(N--){ //每组搬桌子循环
int s,d;
cin>>s>>d; //输入要搬桌子的起点房间号与终点房间号
s=(s-1)/2; //判定房间号对应的数组地址
d=(d-1)/2;
while(s>d){
int temp;
temp=s;
s=d;
d=temp; //若起点房间号大于终点房间号，将其交换一下
}
for(int i=s;i<=d;i++){
p[i]++; //类似于桶排序，在搬桌子过程中经过的房间对应的数组元素++
}
}
int max=-1;
for(int j=0;j<200;j++){
if(p[j]>max)
max=p[j];
} //遍历寻找数组元素最大值,即要使用走廊的最多次数
cout<<max*10<<endl;
}
return 0;
}
二、 可图性判定问题
两个概念：
1.度序列：若吧图G所有顶点的读书排成一个序列S,则称S为图G的度序列。
2.序列是可图的：一个非负整数组成的序列是可图的。
Havel–Hakim定理：主要用来判定一个给定的序列是否是可简单图化的。
判定过程：
（1）对当前数列排序，使其呈递减；
（2）从S[2]开始对其后S[1]个数字-1；
（3）一直循环直到当前序列出现负数（即不可简单图化的情况）或者当前序列全为0 （可简单图化）时退出。
举例：序列S：7,7,4,3,3,3,2,1 删除序列S的首项 7 ，对其后的7项每项减1，得到：6,3,2,2,2,1,0，继续删除序列的首项6，对其后的6项每项减1，得到：2,1,1,1,0，-1，到这一步出现了负数，因此该序列是不可简单图化.
三、 sort函数的使用方法
- 头文件：#include或者使用万能头文件 #include<bits/stdc++.h>
- 语法结构：sort(首地址，尾地址+1，[cmp函数])
- 这个函数可以传两个或者三个参数；
- 第一个参数是要排序的区间首地址；
- 第二个参数是区间尾地址的下一地址；
- 第三个参数不写，则缺省为递增排序。