cfB. Preparation for International Women‘s Day

索引

链接: https://codeforces.com/contest/1133/problem/B.

题解

昨天刚刚做完这道题，说实话当时我思考了一会，想到用余数（n个数据依次对k的余数），例如第一个样例
7 2
1 2 2 3 2 4 10
–>----->------->
1 0 0 1 0 0 0
–>—>---->—>
枚举k的余数：0 ，1，2 ~ k-1
当其中有两个数配对i.e(x,k-x)
即余数(0,0) , (1,k-1) , (2,k-2)
所以只须从n个数据中找出余数为x的数目(设一个条件)以及k-x(与上一个条件互斥)的数目，算出可以成对的数目
发现当两个配对的余数相等时 即x=k-x，上述两个条件同时满足，所以需要单独解决算出可以成对的数目

ac代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;const int N=1e6+10;
string t,s;map<char,int> m1,m2;
int main()
{
    	int n,k,ans=0,i,j,t2=0,t1=0;cin>>n>>k;int a[n];for(i=0;i<n;i++) {
    cin>>a[i];a[i]=a[i]%k;if(a[i]==0)	t1++;}t1/=2;for(i=0;i<n;i++){
    if(a[i]*2==k) t2++;}t2/=2;ans=ans+t1*2+2*t2;for(i=1;i<=k/2;i++){
    t1=0,t2=0;for(j=0;j<n;j++){
    if(2*a[j]==k) continue;if(a[j]==i) t1++;if(a[j]==k-i) t2++;}ans=ans+2*min(t1,t2);}cout<<ans<<endl;return 0;
}