poj 2356

poj 2356

題目大意就是先給出一個數N，接著再給出N個數，要你從這N個數中任意選擇1個或多個數，使得其和是N的倍數

如果找不到這樣的答案 則輸出0

答案可能有多個，但智勇任意輸出一個解就行。

輸出的第一行是選擇元素的個數M，接著M行分別是選擇的元素的值

剛開始的時候並不同為什麼這一題回事抽屜原理，分析後才明白，昨晚後更有體會

實際上此題一定有解，不存在輸出0的結果

證明如下

我們可以依次求出a[0],a[0]+a[1],a[0]+a[1]+a[2],......,a[0]+a[1]+a[2]...+a[n]；

假設分別是sum[0],sum[1],sum[2],......,sum[n]

如果在某一項存在是N的倍數，則很好解，即可直接從第一項開始直接輸出答案

但如果不存在，則sum[i]%N的值必定在[1,N-1]之間，又由於有n項sum，有抽屜原理：

 把多於n個的物體放到n個抽屜裡，則至少有一個抽屜裡有2個或2個以上的物體。

則必定有一對i，j，使得sum[i]%N=sum[j]%N，其中i！=j，不妨設j>i

則（sum[j]-sum[i]）%N=0，故sum[j]-sum[i]是N的倍數

則只要輸出從i+1～j的所有的a的值就是答案

代碼如下：

#include
#include
int main()
{
  int sum[1001000],flag[10010],a[10010],str[10010];
  int n,i,j,t;
  while(scanf("%d",&n)!=EOF)
  {
    memset(sum,0,sizeof(sum));
    memset(flag,0,sizeof(flag));
    for(i=1;i<=n;i++)
      scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
     {
          sum[i]=sum[i-1]+a[i];
          t=sum[i]%n;
          if(t==0)
           {
              printf("%d\n",i);
              for(j=1;j<=i;j++)
               printf("%d\n",a[j]);
               break;
           }
           else
           {
             if(flag[t]==0)
               {
                  flag[t]=1;
                  str[t]=i;
               }
             else
             {
                printf("%d\n",i-str[sum[i]%n]);
                for(j=str[sum[i]%n]+1;j<=i;j++)
                  printf("%d\n",a[j]);
                  break;
             }   
           }
     } 
      
      
  }    
    return 0;
}