注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

UVA 10202  

2010-03-12 12:39:14|  分类: uva |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
经典题目,问题是给你n个数两两相加形成的n*(n-1)个和,求这n个数
假设这n个数分别为ki,则分析可知k1+k2是第一小的数,k1+k3是第二小的数,但不确定k2+k3是第几小,因为k1+k4可能比它小,所以需要枚举k2+k3的位置
假设已经推出前j个数,并把他们的和在n*(n-1)个和减去,然后剩下最小的就是k1+kj+1,便可依次推出其他的
不过代码写的有点丑,囧啊~
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[50],b[50],k[10];
int slove(){
    int sum;
    if(n==3){
      sum=(a[0]+a[1]+a[2]);
      if(sum%2)
        return 0;
      else sum/=2;
      k[0]=sum-a[2];
      k[1]=sum-a[1];
      k[2]=sum-a[0];
      return 1;
    }
    int c[50],mark=0,mm;
    for(int i=2;i<n;i++){
      mark=0;
      memset(b,0,sizeof(b));
      sum=(a[0]+a[1]+a[i]);
      if(sum%2)
        continue;
      else sum/=2;
      k[0]=sum-a[i];
      k[1]=sum-a[1];
      k[2]=sum-a[0];
      for(int j=3;j<=i;j++)
        k[j]=a[j-1]-k[0];
      if(i>2&&k[2]>k[3])
        continue;
      mark=1;
      for(int j1=0;j1<=i;j1++)
        for(int j2=j1+1;j2<=i;j2++){
          mm=0;
          for(int j3=0;j3<n*(n-1)/2;j3++)
            if(!b[j3]&&k[j1]+k[j2]==a[j3]){
              mm=1;
              b[j3]=1;
              break;
            }
          if(!mm)
            mark=0;
        }
     if(!mark)
       continue;
     for(int j=i+1;j<n;j++){
       int tt=0;
       for(int jj=0;jj<n*(n-1)/2;jj++)
         if(!b[jj]){
           tt=jj;
           break;
         }
       k[j]=a[tt]-k[0];
       for(int j1=0;j1<j;j1++){
          mm=0;
          for(int j3=0;j3<n*(n-1)/2;j3++)
            if(!b[j3]&&k[j1]+k[j]==a[j3]){
              mm=1;
              b[j3]=1;
              break;
            }
          if(!mm)
            mark=0;
       }
       if(!mark)
         break;
     }
     if(!mark)
       continue;
     else break;
     }
     if(mark)
       return 1;
     else return 0;
}
int main(){
    while(scanf("%d",&n)!=EOF){
      for(int i=0;i<n*(n-1)/2;i++)
        scanf("%d",&a[i]);
        sort(a,a+n*(n-1)/2);
        if(slove()){
          for(int i=0;i<n-1;i++)
            printf("%d ",k[i]);
          printf("%d\n",k[n-1]);
        }
        else printf("Impossible\n");
    }
    return 0;
}
        

  评论这张
 
阅读(613)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018