贪心

贪心这东西会贯彻你的OI生涯。。。你会在CSP-J中见到ta，你还回在NOI里见到ta（当然你要先过省选

贪心其实就是找到一个最优决策，并每一步都按照决策操作(听起来是不是很simple。。。

如何证明我的贪心是正确的？？？

  1. 你写一下不就知道了？？
  2. 尝试证明做出任何更改都会使结果更劣
  3. 尝试直接数学证明
  4. 尝试感性理解

Example: P1094 [NOIP2007 普及组] 纪念品分组

思路：

对$a$进行排序，定义$l=1,r=n$

每次尝试把al,ara_l,a_r放进当前组，不行则ara_r单独一组

Code:

建议读者自己先Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int w,n;
	cin>>w;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	int l=0,r=n-1,s=0;
	while(l<=r)
	{
		if(a[l]+a[r]<=w)
		{
			l++;
			r--;
		}
		else
			r--;
		s++;
	}
	cout<<s;
	return 0;
}
发现我以前的码风是真的丑qwq

推荐练习：

NOIP 2012 国王游戏

「USACO09OPEN」工作调度 Work Scheduling