Poj 2356(Timus 1032):Find a multiple

Description
The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k).
Input
The first line of the input contains the single number N. Each of next N lines contains one number from the given set.
Output
In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order.

If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them.
Sample Input
5
1
2
3
4
1
Sample Output
2
2
3

这道题的主要意思就是给你N个数,然后从其中找出若干数使其和是N 的倍数。先输出你选择的数的个数,再把数输出。只要输出一组结果就行!

初看这道题,以为会枚举,可是数据太大了了。

后来才知道用的是抽屉原理,并且使问题非常简单。所谓的抽屉原理就是你有三个苹果,两个抽屉,那么至少有一个抽屉里有两个苹果。

可以把前几个数的和加起来,然后对个数取余。然后把余数进行标记,当出现相同的余数时,则我们需要的答案出来了。

在这个题中,

a[1]—–a[5]分别为1,2,3,4,1;

前几个数和分别是:1,3,6,10,11;

然后分别对N(数的个数)取余:1,3,1,0,1;

发现1出现了3次呢,所以可以取a[2]-a[3],则:2,3.

也可以取a[2]-a[5],则2,3,4,1.

以下是代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=10005;
int num[maxn];
int mod[maxn];
int N,sum,flag=0;
int start,end;
void print(int i,int j)
{
    cout<<j-i+1<<endl;
    while(i<=j)
    printf("%d\n",num[i++]);
}
int main()
{
   cin>>N;
   memset(mod,-1,sizeof(mod));
   for(int i=1;i<=N;++i)
    scanf("%d",&num[i]);
   for(int i=1;i<=N;++i)
   {
       sum+=num[i];
       sum%=N;
       if(sum==0)
        {
            print(1,i);flag=1;break;
        }
       if(mod[sum]!=-1)
       {
           start=sum+1;
           end=i;
           print(start,end);
           flag=1;break;
       }
       mod[sum]=i;
   }
   if(flag==0)
   cout<<0<<endl;
   return 0;

}
0

Leave a Reply

Your email address will not be published.