pku 3370 鸽巢原理 .txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define NMAX 100005
//PKU 3370 鸽巢原理 
//注意条件:  c ≤ n 
typedef struct oopsum
{
        int data;
        int where;
}oopsum;
oopsum sum[NMAX];
int shuru[NMAX];

bool cmp(oopsum a,oopsum b)
{
     return a.data<b.data;
}

void solve(int num,int k)
{
     int i,j,min,max;
     sum[0].data=0;
     for(i=1;i<=num;i++)
     {
      sum[i].data=(sum[i-1].data+shuru[i])%k;
      sum[i].where=i;
      } 
      sort(sum+1,sum+1+num,cmp);
      for(i=1;i<=num-1;i++)
      {
       if(sum[i].data==0)
       {//表示1,2....sum[i].where的数的和能被k整除 
         for(j=1;j<=sum[i].where;j++)
          printf("%d ",j);
          printf("\n");
         return;
       }
       else if(sum[i].data==sum[i+1]. data)
       {//表示sum[min].where,sum[min].where+1...sum[max].where的数的和能被k整除 
            if(sum[i].where<sum[i+1].where) 
            {
             min=i;
             max=i+1;
             }
            else 
            {
                 min=i+1;
                 max=i;
                 }
            for(j=sum[min].where+1;j<=sum[max].where;j++)
            printf("%d ",j);
            printf("\n");
            return;
       }
      }
}

int main()
{
 int num,k,i;
 scanf("%d %d",&k,&num);
 while( !(k==0 && num==0))
 
 {
        for(i=1;i<=num;i++) scanf("%d",&shuru[i]);
        solve(num,k);
        scanf("%d %d",&k,&num);
 }
 return 0;    
}