B3830 [NICA #2] 回溯的雨

ljk8886 · 2023-08-22 16:08:25 · 题解

分析

现将 c 数组排序。由于题目中说到，a_ix+y=c_i，即每个 c_i 同余。为了使 y 尽量大，而 x 和 c_i 又是固定的，所以只能让 a_i 尽量小，而 1 \le a_i，所以答案就是 c 数组中最小的数减去 x，即 c_1-x。但是有些情况是无解的，当 c_i 除以 x 不同余或 c_i<x 时，就不可能满足题意，直接特判即可。

注意：不开 long long 见祖宗。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
#define int long long//开long long 
int c[N],n,x;
signed main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    sort(c+1,c+n+1);//排序 
    for(int i=2;i<=n;i++)
    {
        if(c[i]%x!=c[i-1]%x)//判断是否同余 
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    if(c[1]-x<0)cout<<-1<<endl;//判断c数组中的数字是否大于x 
    else cout<<c[1]-x<<endl;
    return 0;
}