Codeforces 876B Divisiblity of Differences:数学【任意两数之差为k的倍数】

题目链接:http://codeforces.com/contest/876/problem/B

题意:

  给你n个数a[i],让你找出一个大小为k的集合,使得集合中的数两两之差为m的倍数。

  若有多解,输出任意一个集合即可。

题解:

  若一个集合中的数,两两之差为m的倍数,则他们 mod m 的值均相等。

  所以O(N)扫一遍,对于每个数a:vector v[a%m].push_back(a)

  一旦有一个集合大小为k,则输出。

AC Code:

 #include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_M 100005 using namespace std; int n,k,m;
vector<int> v[MAX_M]; int main()
{
cin>>n>>k>>m;
int a;
for(int i=;i<n;i++)
{
cin>>a;
v[a%m].push_back(a);
if(v[a%m].size()==k)
{
cout<<"Yes"<<endl;
for(int j=;j<v[a%m].size();j++)
{
cout<<v[a%m][j]<<" ";
}
cout<<endl;
return ;
}
}
cout<<"No"<<endl;
}
上一篇:yum 安装 python-pip 失败解决方法


下一篇:MyEclipse 编写 JSP 代码时很卡的解决办法