算法2--贪心算法

1.老鼠和猫的交易

小老鼠准备了M磅的猫粮，准备去和看守仓库的猫做交易，因为仓库里有小老鼠喜欢吃的五香豆。

仓库有N个房间；
第i个房间有 J[i] 磅的五香豆，并且需要用 F[i] 磅的猫粮去交换；
老鼠不必交换该房间所有的五香豆，换句话说，它可以用 F[i] * a% 磅的猫粮去换取 J[i] * a% 磅的五香豆，其中a是一个实数。

现在，请帮忙计算一下，小老鼠最多能够得到多少磅的五香豆？

输入描述

输入包含多组测试用例。
每组测试数据首先一行是2个非负整数 M 和 N ，接着的 N 行，每行分别包含2个非负整数 J[i] 和 F[i] 。
输入数据以两个-1结束。
题目保证所有的数据不超过1000。

输出描述

请计算并输出小老鼠最多能够得到的五香豆数量。
每组数据输出一行，保留3位小数。

用例输入 1 

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

用例输出 1 

13.333
31.500

 学习：http://t.csdnimg.cn/gcmty

#include<bits/stdc++.h>
using namespace std;
int i;
int m,n;//猫粮数，房间数 
double tot=0;//换后的奶酪数 
struct room{
	double food;
	double cheese;
}a[100000];//数组开大一点 
 
//sort函数的函数部分，从大到小排序 
bool cmp(room x,room y)
{
	return (x.cheese)/x.food>(y.cheese)/y.food;
}
 
int main()
{
	while(scanf("%d %d",&m,&n)!=EOF)
	{
		if(m==-1&&n==-1)	break;//结束条件 
		for(i=1;i<=n;i++)
			cin>>a[i].cheese>>a[i].food;//读入奶酪和猫粮 
			
		sort(a+1,a+1+n,cmp);//注意首地址 
		for(i=1;i<=n;i++)
		{
			if(m-a[i].food>=0)//猫粮多于一只猫需要的猫粮 
			{
				tot=tot+1.0*a[i].cheese;//老鼠得到奶酪增加 
				m=m-a[i].food;//老鼠手中猫粮减少 
			}
			else//按比例购买最后一份猫粮 
			{
				tot=tot+1.0*a[i].cheese/a[i].food*m;
				break;
			} 
		}
		printf("%.3lf\n",tot);
		tot=0;//注意结束后清零 
	}
	return 0;
}

2.田忌赛马

“田忌赛马”是中国历史上一个著名的故事。

大约2300年前，齐国大将田忌喜欢和国王赛马，并且约定：每赢一场，对方就要付200元。

假设已知田忌和国王的各自马匹的速度都不相同，请计算田忌最好的结果是什么。

输入描述

输入包含多组测试样例。
每组样例的第一行是一个整数n(n <= 1000),表示田忌和国王各自参赛的马匹数量。
接下来一行的n个整数表示田忌的马的速度，再接下来一行的n个整数表示国王的马的速度。
n为0时，表示输入数据的结束。

输出描述

每组数据输出一行，表示田忌最多能够赢得的金额。

用例输入 1 

3
92 83 71
95 87 74
2
20 19
22 18
0

用例输出 1 

200
0

一篇非常详细的文章：http://t.csdnimg.cn/qQPsV

题目分析：田忌赛马是一种权衡取舍，找适合策略，来收获最大利益的问题。在本题中我们先将田忌与齐王的马进行排序（在此，我以降序排序），然后选择最优解（比较快马）：

1、田忌>齐王：正常比赛。

2、田忌<齐王：田忌慢马与齐王快马比赛。以慢换快

3、田忌=齐王（这一点十分容易忽略）：这时我们可以观察慢马，若此时田忌>齐王，可以直接让慢马比赛（无疑时必赢的）。若此时田忌<=齐王，将田忌慢马与齐王快马比赛（与慢马或快马进行比赛，都是不可能赢的，何不换取更大的利益）。

#include<bits/stdc++.h>
using namespace std;
 
//sort函数的函数部分，从大到小排序 
bool cmp(int x,int y)
{
	return x>y;
}
 
int main()
{
	int n,a[10000],b[10000];
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)	break; 
		int i,j;
		for(i=0;i<n;i++)	cin>>a[i];
		for(i=0;i<n;i++)	cin>>b[i];
		//从快到慢排序 
		sort(a,a+n,cmp);
		sort(b,b+n,cmp);
		int l1=0,l2=0,sum=0;//排序后的左侧快马 
		int r1=n-1,r2=n-1;//排序后的右侧慢马 
		for(i=0;i<n;i++)
		{
			if(a[l1]>b[l2])//快马：田忌 ＞齐王 ，正常比赛就可以赢 
			{
				l1++;
				l2++;
				sum++;
			}
			else if(a[l1]<b[l2])//快马：田忌＜齐王 ，田忌慢马和齐王快马比赛，包输的 
			{
				r1--;
				l2++;
				sum--;
			}
			else if(a[r1]>b[r2])//快马相等，慢马田忌＞齐王 ，正常比赛就赢了 
			{
				r1--;
				r2--;
				sum++;
			}
			else if(a[r1]<b[l2])//快马相等，慢马田忌＜=齐王 ，田忌慢和齐王快比赛，包输的 
			{
				r1--;
				l2++;
				sum--;
			}
		}
		cout<<sum*200<<endl;
	}
	return 0;
}

3.搬桌子

丁爸信奥培训中心最近在富丽科技大厦租了一层楼，这层楼的形状如下：
 

由图可见，这层楼中间是走廊，两侧各有200个房间，编号如上图。

最近，丁爸信奥培训中心做了内部机构的调整，需要把一些桌子从一个房间搬到另外的房间。因为走廊很窄，但是桌子很大，所以同一段走廊每次只能通过一个桌子。

假设不论远近，每趟搬桌子都需要10分钟。同时，当你从房间i搬桌子到房间j的过程中，房间i到房间j之间的走廊都被占用，也就是说，在每个10分钟内，不能有多个任务共享同一段走廊。

现在，丁爸想知道：要完成所有的搬运任务，最少需要多少时间？

输入描述

输入包含T组测试用例。
每组测试用例首先是一个正整数N（1<=N<=200），表示需要搬运的桌子数量。
接下来N行，每行包含2个正整数s和t,表示需要将一个桌子从房间s搬到房间t。

输出描述

计算并输出完成所有的搬运任务需要的最少的时间，每组数据占一行。

用例输入 1 

3 
4 
10 20 
30 40 
50 60 
70 80 
2 
1 3 
2 200 
3 
10 100 
20 80 
30 50 

用例输出 1 

10
20
30

1. 我们可以把走廊模拟成一条线段，搬运桌子的起始位置模拟成这条线段上的区间；

2. 要想用时尽可能的少，我们应当让在同一时间段搬运的桌子尽可能多，也就是同一时间段线段上互不相交的区间尽可能多；

3. 对于那些存在重叠的区间，我们别无他法，只能分在不同时间段搬运；

4. 因此，我们需要找到区间之间的最大重叠次数，就是我们至少需要的时间；

注意点：由于房间分为两排，1和2, 3和4对应着同一段走廊，所以我们需要通过映射，把房间号对应成相应的走廊号。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,j,n,t,p[201];
	int s,d,temp,k,max;
	cin>>t;
	while(t--)
	{
		for(i=0;i<=200;i++)	p[i]=0;//初识化 
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>s>>d;
			//使房间1和2对应的是一个位置 
			s=(s-1)/2;
			d=(d-1)/2;
			//从号码大的房间往回搬的情况
			if(s>d) 
			{
				temp=s;
				s=d;
				d=temp;
			}
			for(k=s;k<=d;k++)	p[k]++;
		}
		max=-1;
		for(i=0;i<=200;i++)
		{
			if(p[i]>max)	max=p[i];//通过某个地方最大次数为最小时间 
		}
        cout<<max*10<<endl;
	} 
	return 0;	
}

4.今年暑假不AC

作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

输入描述

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Tis​,Tie​ (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

输出描述

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

用例输入 1 

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

用例输出 1 

5

 若干个电视节目，自样例：按结束时选择合适然要按时间顺序来看。为了看更多的节目，需要尽
快看完一个节目再看另外一个节目，多看短节目才能看更多的节目。
        此题贪心的原则是，选择结束时间早的节目，留出时间看更多的节目。因此需要根据节目结束时间排序。

一开始，lastend=count=0，,循环i=0不对，然后改了一下，过了

#include<bits/stdc++.h>
using namespace std;
typedef struct node
{
	int start;
	int end;
}schedule;
 
bool cmp(schedule x,schedule y)
{
	return x.end<y.end;
}
 
int main()
{
	int i,n;
	schedule s[100000];
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)	break;
		for(i=0;i<n;i++)
		cin>>s[i].start>>s[i].end;
		
		sort(s,s+n,cmp);
		int lastend=s[0].end;
		int count=1;
		for(i=1;i<n;i++)
		{
			if(s[i].start>=lastend)
			{
				count++;
				lastend=s[i].end;
			}
		}
		cout<<count<<endl;
	}
	return 0;	
}

5.奋勇争先续

还记得上次那个奋勇争先的题目吗，聪明的你帮助老师找出了第一名的同学。

现在，有个类似的问题：
已知每一位同学的解题数量和罚时，这次希望你能输出排名靠前的若干同学的名单。

注：排名首先依据做题数量，若做题数量相同，则比较罚时，罚时少的排名靠前。

输入描述

第一行是数据组数C，代表有C组测试实例。

每一组数据第一行两个整数N和M，N代表有N个人的成绩，M表示老师需要你输出前M名的名单。

接下来N行，每一行依次给出名字Name，做出的题目数量num和罚时time
( 1<=C<=10, 2<M<=N<=1000, Name的长度最大为10，1<=num<=10， 10<=time<=100000 )

输出描述

每组测试数据输出M行，第i行为第i名的名字、解题数量和罚时，中间用空格隔开。

每组数据后空一行。

用例输入 1 

1
3 3
Bob 5 50
Alice 4 46
John 5 48

用例输出 1 

John 5 48
Bob 5 50
Alice 4 46

#include<bits/stdc++.h>
using namespace std;
struct stu
{
	char name[100];
	int num;
	int time;
}s[1001];
 
bool com(stu a,stu b)
{
	if(a.num<b.num)	return a.num>b.num;//从大到小
	else if(a.num==b.num) 	return a.time<b.time;//从小到大 
}
 
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m,i;
		cin>>n>>m;
		for(i=0;i<n;i++)
			scanf("%s%d %d",s[i].name,&s[i].num,&s[i].time);
		sort(s,s+n,com);
		for(i=0;i<m;i++)
			printf("%s %d %d\n",s[i].name,s[i].num,s[i].time);
		printf("\n"); 
	}
	
	return 0;
} 

6.Degree Sequence of Graph G

Wang Haiyang is a strong and optimistic Chinese youngster. Although born and brought up in the northern inland city Harbin, he has deep love and yearns for the boundless oceans. After graduation, he came to a coastal city and got a job in a marine transportation company. There, he held a position as a navigator in a freighter and began his new life.

The cargo vessel, Wang Haiyang worked on, sails among 6 ports between which exist 9 routes. At the first sight of his navigation chart, the 6 ports and 9 routes on it reminded him of Graph Theory that he studied in class at university. In the way that Leonhard Euler solved The Seven Bridges of Knoigsberg, Wang Haiyang regarded the navigation chart as a graph of Graph Theory. He considered the 6 ports as 6 nodes and 9 routes as 9 edges of the graph. The graph is illustrated as below.

According to Graph Theory, the number of edges related to a node is defined as Degree number of this node.

Wang Haiyang looked at the graph and thought, If arranged, the Degree numbers of all nodes of graph G can form such a sequence: 4, 4, 3,3,2,2, which is called the degree sequence of the graph. Of course, the degree sequence of any simple graph (according to Graph Theory, a graph without any parallel edge or ring is a simple graph) is a non-negative integer sequence?

Wang Haiyang is a thoughtful person and tends to think deeply over any scientific problem that grabs his interest. So as usual, he also gave this problem further thought, As we know, any a simple graph always corresponds with a non-negative integer sequence. But whether a non-negative integer sequence always corresponds with the degree sequence of a simple graph? That is, if given a non-negative integer sequence, are we sure that we can draw a simple graph according to it.?

Let’s put forward such a definition: provided that a non-negative integer sequence is the degree sequence of a graph without any parallel edge or ring, that is, a simple graph, the sequence is draw-possible, otherwise, non-draw-possible. Now the problem faced with Wang Haiyang is how to test whether a non-negative integer sequence is draw-possible or not. Since Wang Haiyang hasn’t studied Algorithm Design course, it is difficult for him to solve such a problem. Can you help him?

输入描述

The first line of input contains an integer T, indicates the number of test cases. In each case, there are n+1 numbers; first is an integer n (n<1000), which indicates there are n integers in the sequence; then follow n integers, which indicate the numbers of the degree sequence.

输出描述

For each case, the answer should be "yes"or “no” indicating this case is “draw-possible” or “non-draw-possible”.

用例输入 1 

2
6 4 4 3 3 2 2
4 2 1 1 1

用例输出 1 

yes
no

可图性的问题

sort()函数中的greater<int>()参数表示将容器内的元素降序排列。不填此参数，默认表示升序排列。

vector<int> a = {1,2,3};
sort(a.begin(), a.end(), greater<int>()); //将a降序排列
sort(a.begin(), a.end()); //将a升序排列

学习：http://t.csdnimg.cn/ENfbk

#include<bits/stdc++.h>
using namespace std;
int a[1006];
 
int havel(int n);
 
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int i,n,flag=0;
		cin>>n;
		for(i=0;i<n;i++)	cin>>a[i];
		if(havel(n)==1)		cout<<"yes"<<endl;
		else 				cout<<"no"<<endl;
	}
	return 0;
} 
 
int havel(int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		sort(a,a+n,greater<int>());//降序排序 
		if(a[0]==0)	return 1;//数组全0退出 
		for(j=1;j<=a[0];j++)
		{
			if(a[j]==0)	return 0;//若为0，-1为负数无法构成简单图 
			else 	a[j]--;
		}
		a[0]=0;//当前点的度清零，会排在最后，不影响有度的点 
	}	
}

贪心算法：

在对问题求解时，总是作出在当前看来是最好的选择，也就是说，不从整体上加以考虑，所作出的仅仅是在某种意义上的局部最优解。

前提：排序。

最长的事件序列问题

可图性判定

1.度序列：若把图G所有顶点的度数排成一个序列S，则称S为图G的度序列。

2.序列是可图的：一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的。

Havel-Hakimi定理:,每趟都要排序。

sort函数

sort（首地址，尾地址+1，[cmp函数]）

1.这个函数可以传两个或三个参数

2.第一个参数是要排序的区间首地址

3.第二个参数是区间尾地址的下一地址

4.第三个参数不写，则缺省为递增排序

若为从大到小排序

int类型

int num[100];
bool cmp(int a,int b)
{
    return a>b;
}
sort(num,num+100,cmp);

结构体类型

struct node
{
    int a;
    double b;
}arr[100];
//先按照a值升序排列，若a值相同，再按b值降序排列。
bool cmp(node x,node y)
{
    if(x.a!=y.a)
        return x.a<y.a;
    return x.b>y.b;
}
sort(arr,arr+100,cmp);

浮点数比较大小不要直接==

double score；
if(fabs(x.score-y.score)>0.00001
    return x.score>y.score;

sort函数可以对数组的某一段进行排序。

若数组中元素是从下标1的位置开始存储，导致忘记修改sort的第一个参数。