B. Preparation for International Women's Day

Love The Way You Lie 2022-03-11 17:18 82阅读 0赞

### 题目描述： ###

International Women’s Day is coming soon! Polycarp is preparing for the holiday.

There are nn candy boxes in the shop for sale. The ii-th box contains didi candies.

Polycarp wants to prepare the maximum number of gifts for kk girls. Each gift will consist of exactly two boxes. The girls should be able to share each gift equally, so the total amount of candies in a gift (in a pair of boxes) should be divisible by kk. In other words, two boxes ii and jj (i≠ji≠j) can be combined as a gift if di+djdi+dj is divisible by kk.

How many boxes will Polycarp be able to give? Of course, each box can be a part of no more than one gift. Polycarp cannot use boxes “partially” or redistribute candies between them.

Input  
The first line of the input contains two integers nn and kk (1≤n≤2⋅105,1≤k≤1001≤n≤2⋅105,1≤k≤100) — the number the boxes and the number the girls.

The second line of the input contains nn integers d1,d2,…,dnd1,d2,…,dn (1≤di≤1091≤di≤109), where didi is the number of candies in the ii-th box.

Output  
Print one integer — the maximum number of the boxes Polycarp can give as gifts.  
题目链接：[http://codeforces.com/contest/1133/problem/B][http_codeforces.com_contest_1133_problem_B]

###### 题意： ######

这个题的意思是给出一个ｎ，ｋ。然后一个ｎ大小的数组ａ。并给ａ数组赋值。  
问：请你将这ｎ个数，两两组成ｋ的倍数。  
即，从n个数中每次选两个数，这两个数的和必须为k的倍数。问最多有多少种可能性。  
分析：  
这个题我看到的时候是懵的。真心不会呀。数据又大。  
后来，经过学长指点。发现这个题根本就没有后效性。～～～内心顿时绝望。一开始我一直在想，如果这个数被选了。那么会不会存在与这个数更好的搭配。后来发现是我想多了。  
但是如果直接暴力的话，数据过大，会超时。  
在深入思考：  
在输入数据的时候，我们就可以将这个数组取余k。然后将其对应位置加1。  
具体见代码：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
       using namespace std;
    int main()
    {
        int digit[101];
        int vis[101];
        int n,k;
        while(~scanf("%d%d",&n,&k))
        {
            memset(digit,0,sizeof(digit));
            memset(vis,0,sizeof(vis));
            for(int i=0;i<n;i++)
            {
                long long a;
                scanf("%I64d",&a);
                int A=a%k;
                digit[A]++;
            }
            int cnt=0;
            for(int i=0;2*i<=k;i++)
            {
                if(i==0||k==2*i)/*如果ｉ等于０的话，那么表示这个数能被k整除。
                看有多少个这样的数，将其两两组合。当如到i*2等于k的时候也是需要这样的。*/
                    cnt+=digit[i]/2;
                else
                {
                 if(digit[i]&&digit[k-i])//i+（k-i）是能整除k的。
                    cnt+=min(digit[i],digit[k-i]);
                }
            }
            printf("%d\n",cnt*2);
        }
    }

[http_codeforces.com_contest_1133_problem_B]: http://codeforces.com/contest/1133/problem/B