Codeforces Round #708 (Div. 2) B. M-arrays 思维+哈希表

  • 原题链接
    Codeforces Round #708 (Div. 2)  B. M-arrays  思维+哈希表
  • 测试样例

    input
    4
    6 4
    2 2 8 6 9 4
    10 8
    1 1 1 5 2 4 4 8 6 7
    1 1
    666
    2 2
    2 4
    output
    3
    6
    1
    1

  • Note

    In the first test case we can divide the elements as follows:
    [ 4 , 8 ] [4,8] [4,8]. It is a 4-divisible array because 4 + 8 4+8 4+8 is divisible by 4 4 4.
    [ 2 , 6 , 2 ] [2,6,2] [2,6,2]. It is a 4-divisible array because 2 + 6 2+6 2+6 and 6 + 2 6+2 6+2 are divisible by 4.
    [ 9 ] [9] [9]. It is a 4-divisible array because it consists of one element.

  • 解题思路
    在这之前,我们再来解释一下题目吧,给定我们一个长度为 n n n的数组 a a a,我们需要将这数组分成好几个数组,其中对于长度大于 1 1 1的数组,都必须满足相邻元素相加能够整除 m m m,我们的任务就是计算我们最小能分成几个数组。实际上这就是一个凑 m m m的题,我们只关心数组中的元素对 m m m的余数,所以我们可以用哈希表将余数都存起来,那么接下来我们怎么最优的分数组呢?就是这样分: x , m − x , x , m − x , x . . . . x,m-x,x,m-x,x.... x,m−x,x,m−x,x....,那么这样必须满足什么条件,我们发现这对互余数它们的数量之差最多为 1 1 1,而对于大于 1 1 1的我们无法分配这么多,那么其余的就要单独开数组分了。 我们按照这样的思路,就可以解题了,遍历我们存储好的余数,统计即可。
  • 代码
/**
* @filename:B.cbp
* @Author : pursuit
* @Blog:unique_pursuit
* @email: 2825841950@qq.com
* @Date : 2021-03-17-22.55.57
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn=1e5+5;
const int mod=1e9+7;

int t,n,m;
map<int,int> p;
void solve(){
    int ans=0;
    if(p[0]){
        //如果存在,就将这些分为一组。
        ans++;
    }
    for(int i=1;i<m;i++){
        if(p[i]){
            //那么我们就需要去寻找它们的互余数数量。
            if(abs(p[i]-p[m-i])<=1){
                //要知道我们构造只能夹着凑,即两个互余数数量之差最多为1.
                ans++;
            }
            else{
                //说明互余数不足,我们需要额外分一数组。
                ans+=abs(p[i]-p[m-i]);
            }
            p[m-i]=0;//避免重复计算。
        }
    }
    cout<<ans<<endl;
}
int main(){
    while(cin>>t){
        while(t--){
            cin>>n>>m;
            p.clear();
            vector<int> a(n);
            for(int i=0;i<n;i++){
                cin>>a[i];
                //记录余数,因为我们只关心能否整除m,对m取余能有效处理,将范围都变成m以内。
                p[a[i]%m]++;
            }
            solve();
        }
    }
    return 0;
}

上一篇:【leetcode】1010. Pairs of Songs With Total Durations Divisible by 60


下一篇:ELK 学习笔记之 elasticsearch 版本控制