贪心并不难，难的是证明。_贪心算法并不难,难的是证明。

$贪心并不难，难的是证明。$
                                                                                                                                                     ———— heidoudou

基本思路：先将数组$sort$一遍，然后用双指针i = 1，j = n，$if(a_i+a_j>w)$，则将$a_j$单独分为一组，--j，$else$则将$a_i$和$a_j$分为一组，++i，--j

证明：

1. $if(a_i+a_j>w)$，$a_j$也不可能和其他任何一个$a_k(i<k<j)$为一组 $\to$ $a_j$单独一组
2. $if(a_i+a_j\le w)${
           $if$ $a_i$，$a_j$各为一组，那么就会比$a_i$，$a_j$为一组的情况多出一组；
           $else$ $if$ $a_i$单独一组，$a_j$与另一个$a_k$为一组，那么$a_j$，$a_k\&a_i$的组数 $=a_j$，$a_i\&a_k$的组数；
           $else$ $if$ $a_j$单独一组，$a_i$与另一个$a_k$为一组，那么$a_i$，$a_k\&a_j$的组数 $=a_i$，$a_j\&a_k$的组数；
           $else$ $if$ $a_i$与$a_k$，$a_j$与$a_m$为一组，交换$a_k\&a_j$后，$⟹a_i+a_j\le w$，$a_k+a_m\le a_k+a_j\le w⟹$
           $a_i$，$a_k\&a_j$，$a_m$的组数 $=a_i$，$a_j\&a_k$，$a_m$的组数；
   }
   $\therefore$ 我们证明看子问题的最优解可以通过上述贪心过程得到

下面我们证明贪心后$\sum$子问题的最优解就是全局最优解

设$a[i...j]$问题为$P$，$P$的贪心解为$S$，经过贪心之后，$\sum$子问题$P^{\prime }$的最优解为$S^{\prime }$。如果$\sum$子问题$P^{\prime }$的最优解$S^{\prime }$不是$P$的最优解，那么我们先假设存在一个最优解$Z$，可以通过上述证明过程后，使之变成相同$\sum$子问题$P^{\prime }$的解$Z^{\prime }$，又$\because S>Z$，而且二者贪心后的分组数是相同的，$\therefore$$S^{\prime }>Z^{\prime }$，这就与$S^{\prime }$为最优解相矛盾，$\to \sum$子问题的最优解 $=$ 全局最优解

$证毕.$

$光知道贪心，贪心为什么可以得到最优解，你证明过么？$
                                                                                                                                                     ———— heidoudou

#include<bits/stdc++.h>
#define ll long long
#define maxn 30005
using namespace std;
inline int read(){
	int x = 0; bool f = false; char ch = getchar();
	while(!isdigit(ch)){if(ch == '-') f = true; ch = getchar();}
	while(isdigit(ch)){x = x * 10 + ch - '0'; ch = getchar();}
	return f ? -x : x;
}
inline void write(ll x){
	if (x < 0) x = ~x + 1, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
int w, n, p[maxn], ans;
int main(){
	w = read(); n = read();
	for(register int i = 1; i <= n; ++i) p[i] = read();
	sort(p + 1, p + n + 1);
	int i = 1, j = n;
	while(i <= j){
		if(p[i] + p[j] > w){++ans; --j;}
		else{++ans; ++i; --j;}
	}
	write(ans); puts("");
	return 0;
}
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