菜鸡刷题比赛日记之数学知识相关
[https://codeforces.com/contest/2007/problem/C](C. Dora and C++)
这题包含加A和加B，此处应该先考虑特殊情况a=b,若不进行如何操作的话，初始答案应该是res=a[n]-a[1](排序之后），然后进行操作，想想该如何最小化极差。为了便于计算，先将数组中每个数字先mod a，因为对于任意的a[n]-a[i],一定可以通过操作将这个差值缩小到[0,a-1],等价于都mod a
归一化之后再考虑如何进行操作，对于目前排序后的数组，0<= qi <= a-1 此时设初始的res = q[n] - q[1],从前往后遍历,显而易见将某个数加上a之后就变成了max。q[1]+a,res=min(res,q[1]+a-q[2]),只可以是q[2]作为目前的最小值，而后从前往后遍历2-n res=min(res,q[i]+a-q[i-1])把前面的数字都加上a之后便可以将q[i-1]设置为最小值
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int gcd(int a,int b)
{
return b? gcd(b,a%b):a;
}
void solve()
{
int n,a,b;scanf("%d%d%d",&n,&a,&b);vector<int>q;
int d=gcd(a,b);
for(int i=1;i<=n;i++)
{
int x;cin>>x;
q.push_back(x%d);
}
sort(q.begin(),q.end());
int ans=q[n-1]-q[0];
for(int i=1;i<n;i++)
{
ans=min(ans,q[i-1]+d-q[i]);
}
cout<<ans<<endl;
}
int main()
{
int t;cin>>t;
while(t--)
{
solve();
}
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
typedef pair<int,int> PII;
int main()
{
int t;cin>>t;
while(t--)
{
int n,k;scanf("%d%d",&n,&k);int mx=-1;
int d[2*k+1]={0};
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
int u=x%(2*k);
d[u]++;
mx=max(mx,x);
}
int cnt=0;int ans=0x3f3f3f3f;
for(int i=0;i<=k-2;i++)cnt+=d[i];
for(int l=0,r=k-1;l<=2*k;l++,r++)
{
if(r==2*k)r=0;
cnt+=d[r];
if(cnt==n)
{
int op=(r-mx)%(2*k);
if(op<0)op+=2*k;
ans=min(ans,mx+op);
}
cnt-=d[l];
}
if(ans==0x3f3f3f3f)cout<<"-1"<<endl;
else cout<<ans<<endl;
}
}