CF 1133B Preparation for International Women's Day

题目链接：http://codeforces.com/problemset/problem/1133/B

题目分析

读完题目，凡是先暴力.....（不用想，第四组数据就TLE了,QAQ)

当两个数的和为k的倍数的时候就凑成一组，那么一定有 (a+b) % k == (a%k + b %k) % k , 而其中对于 a+b 为k的倍数的情况，有(a+b)%k == a%k+b%k - k == 0，我理解为a%k 和 b % k 分别是a,b对凑成数k的贡献。然后，你们也应该想到了，即然满足的组合a%k + b%k == 0，那么我们用数组num[]来存各个数对k取模后的值( x % k )出现的次数，然后，下标之和为k的数就是满足条件的配对，后面就简单了，统计数量就OK 。

代码区

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include <vector>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int Max = 2e5 + 10;

const int mod = 1e9 + 7;

int num[Max];			//记录各个值（value[x]）对k取模后的数的出现次数

int value[Max];

int main()

{

	int n, k;;

	while (scanf("%d%d", &n, &k) != EOF)

	{

		memset(num, 0, sizeof(num));

		for (int i = 1; i <= n; i++)

		{

			scanf("%d", value + i);

			num[value[i] % k]++;	//两数相加后取模和 两数先取模后相加再取模 结果一样

		}

		int sum = num[0] / 2;		//记录可以配对的对数

		if (k % 2 == 0)			//k/2的相加

		{

			sum += num[k / 2] / 2;	//k/2的相加

		}

		int l = 1, r = k - 1;

		while (l < r)

		{

			sum += min(num[l], num[r]);

			l++;

			r--;

		}

		printf("%d\n", 2 * sum);

	}

	return 0;

}

巴特西

CF 1133B Preparation for International Women's Day

题目分析

代码区

最新文章

热门文章