UVA 10202 + HDU 1270 小希的数表

基德KID.1412

KIDx的解题报告
 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1270
 


题意：给出n(n-1)/2个和数（原来n个数的两两之和），求出原来的n个数
黑书《算法艺术与信息学竞赛》30页也有例题解析~~
 
解析：为了研究方便，设这n个整数从小到大依次为A1, A2, A3, ...，也将n(n-1)/2个和数从小到大依次设为K1, K2, K3, ...。
 
①A1+A2总是最小的，A1+A3第二小（想想为什么？）
于是有方程：
A1+A2 = K1;
A1+A3 = K2;
②A2+A3 是不知道的，因为A1+A4等跟他无法比较大小，由于有3个未知数A1, A2, A3，所以要多一条方程才能解出A1, A2, A3，于是枚举A2+A3的和Ki(i > 2)
③由于A1+A4<A1+A5<A1+A6...，所以可以利用A1递推出A4, A5, A6...，整体来说其实就是枚举+暴力检验，一旦检验失败，立刻返回到第一层循环枚举下一个A2+A3的和
④检验方法：设利用和K-A1生成新的数Aj，回去跟A2, A3...Aj-1配对，看是否都有对应的和数，例如看是否存在A1+Aj, A2+Aj...，但是每个和只能用一次，所以需要标记好

下面是UVA 10202的代码，同理HDU 1270也就解决了~

#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <algorithm>using namespace std;#define M 105int main(){int n, m, i, j, k, sum[M], a[15], has[M], s, x;while (~scanf ("%d", &n)){m = n*(n-1) / 2;for (i = 0; i < m; i++) scanf ("%d", sum+i);sort (sum, sum+m);bool flg;for (i = 2; i < m; i++)//枚举sum，令a[2]+a[3] = sum{/****************解方程****************/a[2] = (sum[0] - sum[1] + sum)/2;a[1] = sum[0] - a[2];a[3] = sum[1] - a[1];if (a[2] + a[3] != sum) continue;/****************解方程****************///和标记，0:还没被占用，1:被占用了memset (has, 0, sizeof(has));has = 1;s = 2;flg = true;for (j = 4; j <= n && flg; j++)//递推生成后面的数{while (has) s++;//没被占用的和，生成新数a[j]a[j] = sum - a[1];has = 1;//a[1] + a[j] 占用了sumfor (k = 2; k < j && flg; k++)//检验a[j]+a[k]的和是否存在{for (x = s+1; x < m; x++){if (!has[x] && a[j]+a[k] == sum[x]){has[x] = 1;//和sum[x]被占用break;//a[j]通过检验}}//说明不存在一个可用的和S使得a[j]+a[k] = Sif (x >= m) flg = false;}}if (flg) break;//通过所有检验，成功生成n个数}if (i < m){printf ("%d", a[1]);for (i = 2; i <= n; i++) printf (" %d", a);printf ("\n");}else puts ("Impossible");}return 0;}