Educational Codeforces Round 146 (Rated for Div. 2) D. Balancing Weapons(差分+基础数论)

题目

有n(2<=n<=3e3)把枪，第i把枪有两个参数fi和di(1<=fi<=2e3,1<=di<=1e9)

计pi=fi*di，想在d数组内修改最少的次数，

使得maxpi-minpi<=k(0<=k<=1500)，即pi的极值<=k

注意，di只能被改成正值

求这个最小的修改次数，并输出

实际t(t<=1000)组样例，但保证sumn不超过3e3

思路来源

乱搞ac

题解

赛中数据出锅了，导致没什么人过，虽然unrated&rejudge了，还是贴上了2500的标签

其实看到n=3e3，k=1e5大概就想到n*n+2*n*k的差分了，但是感觉很不好写

首先，手玩发现，

可以把某个pi当最小值（也就是pi+k是允许的最大值），也可以把某个pi当最大值，

此外，最大值max∈[pi，pi+k]也都是合法的，

所以对于每一个枚举的数来说，都有一个长度为k的区间等待校验

对于n个长为k的区间，暴力统计是O(n*n*k)的，用差分干掉一个n，做到O(n*k)

然后就是一堆判断，

1. 对于这个长为k的区间，只有fi>=k+2的才有可能落不进去，否则一定能落入

2. x=r/f[j]*f[j]是能取到的不超过r的f[j]的倍数的最大值

如果x为0（违背d为正值的条件）或者x<l，显然不合法

否则将x和x-f[j]的位置做标记，表示合法区间必须覆盖x或x-f[j]，否则这个数就没落在区间里

区间是从[pi,pi+k]逐步往下枚举的，最终枚举到[pi-k,pi]，考虑区间的并，长度为2k

2k的区间放入每f[j](f[j]>=k+2)才出现一次的数，最多放两个

所以，x-f[j]的情况有可能有，有可能没有

只有x-f[j]>0(减去一个f[j]后可能会导致d为0，=0就不合法了)且x-f[j]>=l，才是需要考虑x-f[j]的

3. 差分数组nd维护必须落入的数，

也就是上面提到的f[j]>=k+2，区间必须要覆盖的数

差分数组add维护可以不挪的数，

也就是正好可以落在[pi-k,pi+k]内的数，记为tmp，n-tmp就是需要修改的数的个数

遍历差分数组，只有必须覆盖的数都覆盖了，才可以用n-tmp更新答案

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef unsigned ui;
//typedef __uint128_t L;
typedef unsigned long long L;
typedef unsigned long long ull;
const int N=3e3+10;
int t,n,k,f[N],d[N];
int sol(int p){
    int res=n;
    vector<int>add(2*k+5,0),nd(2*k+5,0);
    ll mid=1ll*f[p]*d[p],l=mid-k,r=mid+k;//[w,w+k]
    int tmp=1,cnt=0,now=0;
    rep(j,1,n){
        if(j==p)continue;
        ll v=1ll*f[j]*d[j];
        if(l<=v && v<=r)add[r-v]++;
        tmp+=(mid<=v && v<=r);
        if(f[j]>=k+2){
            cnt++;
            ll x=r/f[j]*f[j];
            if(!x || x<l)return res;
            nd[r-x]++;
            if(x-f[j] && x-f[j]>=l)nd[r-(x-f[j])]++;
            now+=(mid<=x && x<=r);
        }
    }
    if(now==cnt)res=min(res,n-tmp);
    rep(j,1,k){
        now-=nd[j-1];
        tmp-=add[j-1];
        tmp+=add[j+k];
        now+=nd[j+k];
        if(now==cnt)res=min(res,n-tmp);
    }
    return res;
}
int main(){
    sci(t);
    while(t--){
        sci(n);sci(k);
        rep(i,1,n)sci(f[i]);
        rep(i,1,n)sci(d[i]);
        int ans=n;
        rep(i,1,n)ans=min(ans,sol(i));
        printf("%d\n",ans);
    }
    return 0;
}
/*
3 5
19 11 9
13 63 731
*/