基本原理:n+1只鸽子飞回n个鸽笼至少有一个鸽笼含有不少于2只的鸽子。
很简单,应用却也很多,很巧妙,看例题:
Description
Every year there is the same problem at Halloween: Each neighbour is only willing to give a certain total number of sweets on that day, no matter how many children call on him, so it may happen that a child will get nothing if it is too late. To avoid conflicts,
the children have decided they will put all sweets together and then divide them evenly among themselves. From last year's experience of Halloween they know how many sweets they get from each neighbour. Since they care more about justice than about the number
of sweets they get, they want to select a subset of the neighbours to visit, so that in sharing every child receives the same number of sweets. They will not be satisfied if they have any sweets left which cannot be divided.
Your job is to help the children and present a solution.
Input
The input contains several test cases.
The first line of each test case contains two integerscandn(1 ≤ c ≤ n ≤ 100000), the number of children and the number of neighbours, respectively. The next line containsnspace
separated integersa1, ... ,an(1 ≤ ai≤ 100000), whereairepresents the number of sweets the children get if they visit
neighbouri.
The last test case is followed by two zeros.
Output
For each test case output one line with the indices of the neighbours the children should select (here, indexicorresponds to neighbouriwho gives a total number ofaisweets).
If there is no solution where each child gets at least one sweet print "no sweets" instead. Note that if there are several solutions where each child gets at least one sweet, you may print any of them.
Sample Input
4 5
1 2 3 7 5
3 6
7 11 2 5 13 17
0 0
Sample Output
3 5
2 3 4
Source
题目大意:糖果平分问题。有c个小孩,n个提供糖果的邻居,你可以选择要或不要。现在你只考虑得到的全部糖果能否平分,可能有多种方案,输出一种即可。
上面的case 1: 结果 2 3 4 也行,总和为12. 输出一种即可
#include <stdio.h>
#include <algorithm>
using namespace std;
int c,n,neigb[100001];
int S;
struct Remnant
{
int h,r; // 下标和余数
}R[100001];
bool cmp(const Remnant &a, const Remnant & b){ //按余数从小到大排序
if( a.r == b.r)
return a.h < b.h;
return a.r < b.r;
}
int main(){
//freopen("in.txt","r",stdin);
while(scanf("%d %d", &c, &n) != EOF){
if(c==0 && n==0) break;
int k=-1,h;
S=0;
for(int i=0; i<n; i++)
{
scanf("%d",&neigb[i]);
S += neigb[i];
R[i].r = S%c; //存储是前i个和 对c的余数
R[i].h = i + 1; //h 为下标
if(k == -1 && R[i].r==0 ) k=i;
}
if(k == -1){
sort(R, R+n, cmp);
for(int i=0; i<n-1; i++)
{
if(k == -1 && R[i].r == R[i+1].r)
{
k = R[i].h;
h = R[i+1].h;
break;
}
}
if(k==-1)
printf("no sweets\n");
else{
for(int i=k+1; i<h; i++)
printf("%d ",i);
printf("%d\n",h);
}
}else{
for(int i=0; i<k; i++)
printf("%d ",i+1);
printf("%d\n",k+1);
}
}
return 0;
}
分享到:
相关推荐
数学广角-鸽巢问题--整理复习.doc
人教版数学六年级下册鸽巢原理-康淼.pdf
重点介绍鸽巢原理的应用,在组合数学中鸽巢原理的定义及其主要应用
组合数学中鸽巢原理又称为抽屉原理,在此文章中包含了丰富的例子及详解
用java编译的鸽巢原理,里面有成功运行的源文件和关于鸽巢原理的文档。
组合数学相关知识,包括容斥原理及其应用,鸽巢原理及其应用,
数学广角——鸽巢原理1PPT课件.pptx
文章以小学生可以理解的语言,从鸽巢原理的简介、应用、实战演练、数学证明和扩展等多个方面进行了详尽的讲解,旨在帮助初学者快速理解并掌握鸽巢原理的基本概念和应用场景。 适用人群: 本篇文章主要面向初学者,...
鸽巢原理 鸽巢原理 鸽巢原理 鸽巢原理 鸽巢原理
人教版六年级数学下册鸽巢原理练习题及答案精选.doc
鸽巢原理,又称为抽屉原理,是组合数学中一个非常基础且重要的原理。它描述了一种简单的数学现象:当足够多的物体被放入有限数量的容器中时,至少有一个容器包含两个或更多的物体。这一原理在日常生活、科学研究以及...
鸽巢原理
容斥原理与鸽巢原理。在求解计数问题时,用间接的方法往往比直接容易,本课件将介绍常用的间接计数方法: 容斥原理与鸽巢原理.
鸽巢原理
鸽巢原理
鸽巢原理
鸽巢原理 演示如何使用鸽巢原理来解决一个问题