本文主要是介绍2023NOIP A层联测28-大眼鸹猫,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
给你两个长度为 n n n 的序列 a , b a,b a,b,这两个序列都是单调不降的。
你可以对 a a a 进行不超过 m m m 次操作,每次操作你可以选择一个 i i i 满足 1 ≤ i ≤ n 1\le i\le n 1≤i≤n,然后选择一个整数(可以是负数) x x x,将 a i a_i ai 加上 x x x,这一次操作需要花费 x 2 x^2 x2 的代价。
在做操作的过程中,你需要保证 a a a 始终单调不降。
最后,你需要将 a a a 序列变成 b b b 序列,即对任意 i i i 满足 1 ≤ i ≤ n 1\le i\le n 1≤i≤n,都有 a i = b i a_i=b_i ai=bi。
求最小需要花费的总代价之和。
n , m ≤ 1 0 5 n,m\le10^5 n,m≤105
首先如果 m m m 小于 a i ≠ b i a_i\not=b_i ai=bi 的个数,就是无解了。
操作过程中,要保证 a a a 始终单调不降,看上去很难满足,但结论是一定存在一种合法操作方案。可以考虑一个极大的区间 [ l , r ] [l,r] [l,r], ∀ i ∈ [ l , r ] , a i < b i \forall i\in[l,r],a_i< b_i ∀i∈[l,r],ai<bi,此时就从 r r r 操作到 l l l,若 ∀ i ∈ [ l , r ] , a i > b i \forall i\in[l,r],a_i>b_i ∀i∈[l,r],ai>bi,就从 l l l 操作到 r r r。
所以单独考虑每一个数 ∣ a i − b i ∣ |a_i-b_i| ∣ai−bi∣,分配了 x i x_i xi 次操作,显然每次操作将 ∣ a i − b i ∣ |a_i-b_i| ∣ai−bi∣ 减少 ∣ a i − b i ∣ x i \dfrac{|a_i-b_i|}{x_i} xi∣ai−bi∣ 是代价最小的。设 f ( x ) f(x) f(x) 表示给 ∣ a i − b i ∣ |a_i-b_i| ∣ai−bi∣ 分配了 x x x 次操作的最小代价,发现 f ( x ) f(x) f(x) 是下凸函数,意思是随着 x x x 的增大, f ( x ) f(x) f(x) 减小的幅度越来越小。
那么我们可以先给每个数分配一次操作,对于剩下的操作用大根堆维护每个数再分配一次操作减少的代价,每次就贪心的去选代价减少得最多的,然后给它分配一次操作再放进堆里。最后把堆里的数拿出来算答案即可。
时间复杂度 O ( m log n ) O(m\log n) O(mlogn)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int N=1e5+1;
constexpr ll mod=998244353;
int n,m;
ll a[N],b[N],dis[N],ans;
inline ll getval(ll x,ll n)
{return (x/n)*(x/n)*(n-x%n)+(x/n+1)*(x/n+1)*(x%n);
}
struct node
{int num,id;bool operator<(const node &a)const{return getval(dis[id],num)-getval(dis[id],num+1)<getval(dis[a.id],a.num)-getval(dis[a.id],a.num+1);}
};
priority_queue<node> q;
int main()
{freopen("attend.in","r",stdin);freopen("attend.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];int fl=0;for(int i=1;i<=n;i++) fl+=(a[i]!=b[i]);if(fl>m) cout<<"-1",exit(0);for(int i=1;i<=n;i++){if(a[i]==b[i]) continue;dis[i]=abs(a[i]-b[i]);q.push({1,i});}if(q.empty()) cout<<0,exit(0);m-=fl;while(m--){node now=q.top();q.pop();now.num++;q.push(now);}while(q.size()){ans=(ans+getval(dis[q.top().id],q.top().num))%mod;q.pop();}cout<<ans;
}
这篇关于2023NOIP A层联测28-大眼鸹猫的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!