链接:https://acm.ecnu.edu.cn/problem/3673/
思路:通过暴力枚举a2+a3的值,算出a1,a2,a3,同时删除a1+a2,a1+a3,a2+a3,剩下的元素中最小的就是a1+a4,可以计算出a4,再删除a1+a4,a2+a4,a3+a4,剩下的最小的就是a1+a5,又可以算出a5,以此类推即可。复杂度(n^3logn),用multiset可以很简单的写出这个题。
代码:
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
|
#include<bits/stdc++.h> using namespace std;
int T; typedef long long ll; multiset<ll> s1,s2; int n; const int maxn = 1e6; ll a[maxn]; ll b[maxn];
bool (ll sum){ if((sum+a[1]-a[2])%2)return false; if((sum+a[2]-a[1])%2)return false; b[2] = (sum+a[1]-a[2])/2; b[3] = (sum+a[2]-a[1])/2; b[1] = a[1]-b[2]; s2.erase(s2.find(a[1])); s2.erase(s2.find(a[2])); s2.erase(s2.find(sum)); int nn = 3; while(nn<n){ ll minv = 1e18; for(auto &it:s2){ minv = min(minv,it); } b[nn+1] = minv-b[1]; for(int i=1;i<=nn;i++){ if(!s2.count(b[i]+b[nn+1]))return false; s2.erase(s2.find(b[i]+b[nn+1])); } nn++; } return true; }
int main(){ scanf("%d",&T); while(T--){ s1.clear(); scanf("%d",&n); for(int i=1;i<=n*(n-1)/2;i++){ scanf("%lld",&a[i]); s1.insert(a[i]); } for(int i=3;i<=n*(n-1)/2;i++){ s2 = s1; if(check(a[i])){ for(int i=1;i<=n;i++)printf("%lld ",b[i]); puts(""); break; } } } return 0; }
|
近期评论