codeforces 1374D（数学）

dejavu1zz

发布于 2020-10-23 15:18:55

3120

发布于 2020-10-23 15:18:55

文章被收录于专栏：奇妙的算法世界

题意描述

You are given an array a consisting of n positive integers.

Initially, you have an integer x=0. During one move, you can do one of the following two operations:

Choose exactly one i from 1 to n and increase ai by x (ai:=ai+x), then increase x by 1 (x:=x+1). Just increase x by 1 (x:=x+1). The first operation can be applied no more than once to each i from 1 to n.

Your task is to find the minimum number of moves required to obtain such an array that each its element is divisible by k (the value k is given).

You have to answer t independent test cases.

给定n个数字，你有一个x，可以对x进行两种操作，询问最少的操作次数，使得n个数都为k的倍数。

思路

我们可以从取模的性质来考虑，如果一个数%k为0，那么不用进行任何操作，如果出现了%k不为0，很明显可以看出需要进行的操作次数为k*余数出现的次数-xi。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=2*1e5+10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int a[N];
map<LL,LL> cnt;
void solve(){
    cnt.clear();
    int n,k;cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]%=k;
    }
    LL ans=0;
    for(int i=0;i<n;i++){
        if(!a[i]) continue;
        cnt[a[i]]++;
        ans=max(ans,(LL)cnt[a[i]]*k-a[i]);
    }
    if(ans) ans++;
    cout<<ans<<endl;
}
int main(){
    IOS;
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/08 ，如有侵权请联系 cloudcommunity@tencent.com 删除

element