[贪心]救救曹植 qduoj22Spring8

Description

曹植是三国时期著名文学家，被谢灵运称之为”天下才有一石，曹子建独占八斗“。但可惜的是，他和他的哥哥曹丕关系不好。

这天在曹丕的疯狂push之下，曹植七步成诗，写出了”本是同根生，相煎何太急“之句。曹丕心想：这七步成诗是我的idea，你通讯作者不挂我就算了，还敢内涵我迫害兄弟。我刚当皇帝，受得了这委屈？今天一定要让你知道知道厉害！

于是曹丕让人呈上标号为1 ~ n的n个杯子。每个杯子里装有ai个豆子。然后对曹植说：“现在你要用最少的次数把杯子里的豆子取光。取豆方式是，每次选一个编号x，然后从编号为x, 2 * x, 2 * x + 1的杯子中分别取一个豆子。如果杯子里没有豆子了，那就不用取；你不能在编号之外的杯子里取豆，所以2*x + 1  ≤ n。”

”如果你能做到，就将所取之豆放进釜中，你我兄弟今日饮宴就吃豆羹；如果你做不到，那今日在釜中哭泣的就不是豆子了“。

聪明如你，能帮曹植解决这个问题吗？

Input

第一行包含一个整数n (1 ≤n≤ 100)表示杯子数目。

第二行包含n个由空格隔开的整数：a1, a2, a3, ...., an(1 ≤ ai≤ 1000)，其中ai表示开始时杯子中豆子的数目。

Output

如果可以将所有豆子取光，输出一个整数表示取豆子所需的最少次数。

如果不能将所有豆子取光，输出-1

Sample Input 1 

2
1 1

Sample Output 1

-1

Sample Input 2 

3
868 762 256

Sample Output 2

868

题意： 有n个杯子，每个杯子中放有a[i]个豆子，每次可以从编号为x，2*x，2*x+1的杯子中取出一个豆子，如果2*x+1超出边界那就不能取，杯子中没有豆子时也可以取，问最终把豆子取完最少多少次。

分析： 一开始考虑正着贪心，每次把i的杯子取到0，如果最后还有豆子就说明不可能取完。后来发现这样是错的，因为在杯子为空时还可以取，这样最终总是能取完的，可以画出一张图，这就是从1~9时所有能取的操作，可以发现如果n为偶数那么一定无法取完，如果n是奇数就总能取完。

画出图来就很直观了，在从前往后贪心时把a[i]变成0实际上有两种方式，要么是让i作为x去取，要么是让i作为2*x或2*x+1去取，这两种方式都能把a[i]取到0，但具体哪种更好其实是不确定的，例如上图中取到4时，如果4中还不为0那么可以选择取(2, 4, 5)或者(4, 8, 9)。但如果考虑从后往前贪心，9这个位置只有一种方式取完，也就是无论之后如何选择一定会存在a[9]次选取(4, 8, 9)，为了达到最优可以先处理这些一定会进行的操作，同理8、7、6、5都是这样的，当到4这里时存在两种选取方式了，但是一定是选(2, 4, 5)更优，因为4后面的杯子都为空了，选(4, 8, 9)显然会造成浪费，也就是无论之后如何选择一定会存在a[4]次选取(2, 4, 5)，于是为了最优先把这些次数取完，在3、2处同理。最后在1处只有一种选取方式，就只能选(1, 2, 3)直到1为空。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;int a[105];signed main()
{int n;cin >> n;for(int i = 1; i <= n; i++)scanf("%d", &a[i]);if(n%2==0 || n <= 2) puts("-1");else{int ans = 0;for(int i = n; i >= 1; i--){if(a[i] > 0){if(i&1){a[i-1] -= a[i];a[i/2] -= a[i];}else{a[i+1] -= a[i];a[i/2] -= a[i];}ans += a[i];a[i] = 0;}}cout << ans;}return 0;
}