2023NOIP A层联测28 T3 大眼鸹猫
比赛做出来了,但是文抄……
思路
分析每一个 \(i\),发现其一定需要上升或下降 \(|a_i-b_i|\)。
如果求出最小操作次数,然后在此基础上,将上升或下降操作分成多次,减小对答案的贡献即可。
最小操作次数
从后向前考虑,若 \(a_i\) 需要下降,那么先不管它;若 \(a_i\) 要上升,那么立刻上升。
如果 \(i\) 要上升,此时对于 \(i+1\) 而言,要么等待下降,要么已经上升完毕,这两种情况都可以保证操作后的 \(a_i \leq a_{i+1}\)。
执行完上升后,从前向后考虑,此时要上升的 \(a_i\) 已经不存在,若 \(a_i\) 要下降,直接下降即可。
这里可以发现,最多只需要 \(n\) 次操作即可使 \(a_i=b_i\),且发现,对于每一个操作都是独立的。
Ps:独立性对减小贡献有很大帮助。
最小答案
考虑对于 \(a_i\) 使用 \(x\) 次操作的最小贡献。易得,把 \(a_i\) 等分成 \(x\) 份后,再进行 \(x\) 次上升,可以得到最小贡献。
一开始每一个 \(a_i\) 都分了 \(1\) 次操作。
可以记录一下,如果给 \(a_i\) 多一次操作会减少多少贡献,每次取最大者即可。
具体实现就是,开一个优先队列,以 \(a_i\) 多一次操作减少的贡献为关键字,每次取队头。取出后将分配次数加一,然后再入队多一次操作减少的贡献,直到 \(m\) 次操作用完。
注意对于 \(a_i=b_i\) 的情况,不算操作次数。
CODE
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define ll long long
#define S second
#define F first
const int maxn=3e5+5;
int n,m;
int a[maxn],b[maxn],cd[maxn];
ll now[maxn],t[maxn];
priority_queue< pair<ll,int> >que;
ll sqr(ll x){return x*x;}
int main()
{
freopen("attend.in","r",stdin);
freopen("attend.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
{
cd[i]++;
t[i]=abs(a[i]-b[i]);
if(t[i]==0) {m++,cd[i]=0;continue;}
now[i]=sqr(t[i]);
que.push( make_pair(now[i]-
(sqr((t[i])/(cd[i]+1))*((cd[i]+1)-t[i]%(cd[i]+1))+
sqr(t[i]/(cd[i]+1)+1)*(t[i]%(cd[i]+1))),i) );
}
m-=n;
if(m<0) printf("-1"),exit(0);
while(m&&!que.empty())
{
m--;
pair<ll,int>x=que.top();
if(x.first==0) break;
que.pop();
now[x.S]-=x.F;
cd[x.S]++;
int i=x.S;
que.push( make_pair(now[i]-
(sqr((t[i])/(cd[i]+1))*((cd[i]+1)-t[i]%(cd[i]+1))+
sqr(t[i]/(cd[i]+1)+1)*(t[i]%(cd[i]+1))),i) );
}
ll ans=0;
for(int i=1;i<=n;i++) ans=(ans+now[i])%mod;
printf("%lld",ans);
}
麻麻的,文抄写错哩。