紫书 习题8-10 UVa 1614 (贪心+结论)

时间:2021-08-19 09:34:54

这道题我苦思冥想了一个小时, 想用背包来揍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;
}