紫书习题8-10 UVa 1614 （贪心+结论）

这道题我苦思冥想了一个小时，想用背包来揍sum/2，然后发现数据太大，空间存不下。

然后我最后还是去看了别人的博客，发现竟然有个神奇的结论……

幸好我没再钻研，感觉这个结论我肯定是想不到的……

结论是：在1 <= a[i] <= i时，前i个数一定可以凑出1~sum[i]的所有整数

证明看这 https://blog.csdn.net/wcr1996/article/details/43957461

其他博客写有了这个结论，就排序一下，从大到小，凑sum/2，能凑就凑，最后一定可以凑成。

但是我开始一直想不通为啥这样下去一定可以凑成，为什么要排序？？其他博客貌似没有

给出解释……

然后我自己思考了挺久，想通了。

首先这个结论证明一定可以揍成sum/2（sum为奇数不考虑，输出No）

然后，从大到小排序。

假设第一个可以凑的数为a[k]， a[k]显然是第一个小于等于sum/2的数

也就是说a[k]之前的数，也就是所有大于a[k]的数，都大于sum/2

也就是说这些数不可能来揍sum/2.

然后sum/2就减去了a[k]。那么a[k]之后的数一定可以凑sum/2-a[k]；

为什么呢？这里是关键。

因为要凑sum/2-a[k]的数字肯定小于sum/2-a[k]，而这些数字一定在a[k]之后

因为a[k]是第一个小于等于sum/2的数，那么第一个小于等于sum/2-a[k]的数字

肯定小于等于a[k]，也就肯定在a[k]后面。

所以要凑成sum/2-a[k]的数都在a[k]后面，这些数字还没有被选到。

因为开始的结论说明肯定可以凑sum/2-a[k]，而所有需要来凑

sum/2-a[k]的数还没有遍历到。

所以， sum/2-a[k]一定可以用还没遍历到的数凑成。

以此类推，一直做下去，肯定可以凑完

over！！！！！！！！！！

#include<cstdio>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112345;

int a[MAXN], id[MAXN], n;

bool cmp(int x, int y)

{

	return a[x] > a[y];

}

int main()

{

	while(~scanf("%d", &n))

	{

		long long sum = 0;

		REP(i, 0, n)

		{

			scanf("%d", &a[i]);

			sum += a[i];

			id[i] = i;

		}

		if(sum & 1) { puts("No"); continue;	}

		sort(id, id + n, cmp);

		sum >>= 1;

		REP(i, 0, n)

		{

			int t = id[i];

			if(a[t] <= sum)

			{

				sum -= a[t];

				a[t] = 1;

			}

			else a[t] = -1;

		}

		puts("Yes");

		REP(i, 0, n) printf("%d ", a[i]);

		puts("");

	}

	return 0;

}

巴特西

紫书习题8-10 UVa 1614 （贪心+结论）

最新文章

热门文章

巴特西

紫书 习题8-10 UVa 1614 （贪心+结论）

最新文章

热门文章

紫书习题8-10 UVa 1614 （贪心+结论）