洛谷P1286 两数之和

这个题。。刚开始没看见输入若干行，所以有的点就。。

令 m = n * (n - 1) / 2

已知 s = {s (1), s(2), ..., s(m)}，

s(i) <= s(i+1)

那么

最小是 s1=x1+x2，

其次是 s2=x1+x3，

则有 sp=x2+x3

联立解得：(s1 + s2 + sp) / 2 - sp = x1

s[]=s-{x1+x2, x1+x3, x2+x3}

也就是将s[]中的求得的点打上标记

x1 + x4 = min{s}，求出x4

s = s - {x1 + x4, x2 + x4, x3 + x4}

也是将能求出的点打上标记

x1+x5=min{s}... （以此类推）

另外需要判断常数列：

1.如果是奇数列，就无解，输出Impossible

2.如果是偶数列，就输出n个，s[1] / 2。

处理的话用了一下二分，找第一个不小于k的位置

我没用搜索，通过上面的解析，放到循环中就好了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 310;

const int maxm = maxn * (maxn-1) / 2;

int n,m,x[maxn],s[maxm];

int cnt,ans[2][maxn];

bool vis[maxm];

int flag=1;

int erf(int k){

    //找不小于k的最小值

    int l = 0 , r = m + 1 , ans , mid;

    while(r > l + 1){

        mid = (l + r) / 2;

        if(s[mid] < k)  ans = l = mid;

        else r = mid;

    }

    return ans + 1;

}

void find(int p){

    memset(vis,false,sizeof(vis));

    vis[1] = vis[2] = vis[p] = true;

    x[1] = (s[1] + s[2] + s[p]) / 2 - s[p];

    x[2] = s[1] - x[1];

    x[3] = s[2] - x[1];

    int next = 3;

    for(int i=4;i<=n;i++){

        while(next < m && vis[next])

          next++;

        //if(next > m)  return;

        x[i] = s[next] - x[1];

        vis[next] = true;

        for(int j=2;j<i;j++){

            if(x[j] > x[i])  return;

            int sum = x[i] + x[j];

            p = erf(sum);

            if(s[p] != sum)  return;

            bool found = false;

            for(int k=p;p<=m && s[k] == s[p];k++){

                if(!vis[k]){

                    found = true;

                    vis[k] = true;

                    break;

                }

            }

            if(!found)  return;

        }

    }

    for(int i=1;i<=n;i++)

      ans[1][i] = x[i];

    cnt++;

}

int main(){

    while(scanf("%d",&n) == 1){

        memset(ans,0,sizeof(ans));

        memset(x,0,sizeof(x));

        flag=1;cnt=0;

        m = n * (n - 1) / 2;

        for(int i=1;i<=m;i++){

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

            if(i>1){

	            if(s[i]==s[i-1]&&flag==1) flag=1;

                else flag=0;

            }

        }

        if(flag){

            //printf("1\n");

            if(s[1] % 2 == 0){

               for(int i=1;i<=n;i++)

                 printf("%d ",s[i] / 2);

                printf("\n");

            }

            else {

                printf("Impossible\n");

            }

        }

        else{

            sort(s + 1,s + m + 1 );

            for(int i=3;i<=m;i++){

                if((s[i] != s[i-1] || i==3) && (s[1] + s[2] + s[i]) % 2 == 0)

                  find(i);

                if(cnt > 0)

                  break;

            }

            if(cnt == 0) {

                printf("Impossible\n");

            }

            else {

                for(int j=1;j<=n;j++)

                printf("%d ",ans[1][j]);

                printf("\n");

            }

        }

    }

    return 0;

}

巴特西

洛谷P1286 两数之和

最新文章

热门文章