题解：P10556 [ICPC2024 Xi'an I] Make Them Straight
yywlp
·
·
题解
挺有意思的题。
题目中 0\le a_i\le 10^6 是非常重要的限制，因为这让我们可以枚举 k。显然当
(i-1)\times k\ge 10^6
的时候后面的 a_i 一定都不满足了，那么设 M=10^6，每次其实只用枚举前 \frac{M}{k} 个 a_i 即可，这个形式刚刚好是调和级数，复杂度 \Theta(M\log M)。
又通过题目中的定义：
发现这其实是一条直线 $y=kx+b$。
其中 $k$ 就是题中的 $k$，$b$ 就是 $a_1$。
所以枚举 $k$，枚举 $a_i$，当 $(i-1)\times k\ge 10^6$ 时停止枚举，同时以 $a_i-(i-1)\times k$ 为下标，$b_i$ 为值，开个桶存一下看哪个 $a_1$ 可以使直线碰到的点价值总和最大即可。
复杂度即为开始所说的 $\Theta(M\log M)$。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e6+10;
int n;
int a[M],b[M],sum=0;
int p[4*M];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]),sum+=b[i];
int ans=1e18;
for(int i=0;i<=1e6;i++){
for(int j=1;(j-1)*i<=1e6&&j<=n;j++)p[a[j]-(j-1)*i+2*M]+=b[j],ans=min(ans,sum-p[a[j]-(j-1)*i+2*M]);
for(int j=1;(j-1)*i<=1e6&&j<=n;j++)p[a[j]-(j-1)*i+2*M]-=b[j];
}
cout<<ans<<endl;
}
```