程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2356 Find a multiple 鴿巢原理

POJ 2356 Find a multiple 鴿巢原理

編輯:C++入門知識

題意:有n個數,求是否存在一些數的和是n的倍數。若存在,輸出即可。不存在,輸出0.
思路:鴿巢原理的題目,組合數學課本上的原題。可以把和求出來,然後對n取余,因為有n個和,對n取余,如果余數中沒有出現0,根據鴿巢原理,一定有兩個數的余數相同,兩個和想減就是n的倍數。如果余數出現0,自然就是n的倍數。也就是說,n個數中一定存在一些數的和是n的倍數。求余輸出即可。
代碼:
[cpp]
#include <iostream> 
#include <cstdio> 
#include <string.h> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
const int N = 10010; 
int num[N],sum[N],pos[N]; 
bool flag[N]; 
int main(){ 
    //freopen("1.txt","r",stdin); 
    int n; 
    while(scanf("%d",&n) != EOF){ 
        CLR(num,0); 
        CLR(sum,0); 
        CLR(pos,-1); 
        CLR(flag,false); 
      for(int i = 1; i <= n; ++i){ 
          scanf("%d",&num[i]); 
          sum[i] = sum[i-1] + num[i]; 
      } 
      for(int i = 1;i <= n; ++i){ 
        int x = sum[i] % n; 
        if(flag[x]){ 
          int y = pos[x]; 
          printf("%d\n",i - y); 
          for(int j = y+1; j <= i; ++j) 
              printf("%d\n",num[j]); 
          break; 
        } 
        if(x == 0){ 
          printf("%d\n",i); 
          for(int j = 1; j <= i;++j) 
              printf("%d\n",num[j]); 
          break; 
        } 
        flag[x] = true; 
        pos[x] = i; 
      } 
    } 
    return 0; 

 


作者:wmn_wmn

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved