湖州微网站建设,连云港关键字优化案例,如何做一个个人网页,wordpress 遍历文章给你两个长度为 n n n 的序列 a , b a,b a,b#xff0c;这两个序列都是单调不降的。
你可以对 a a a 进行不超过 m m m 次操作#xff0c;每次操作你可以选择一个 i i i 满足 1 ≤ i ≤ n 1\le i\le n 1≤i≤n#xff0c;然后选择一个整数#xff08;可以是负数这两个序列都是单调不降的。
你可以对 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_ib_i aibi。
求最小需要花费的总代价之和。 n , m ≤ 1 0 5 n,m\le10^5 n,m≤105 首先如果 m m m 小于 a i ̸ b i a_i\notb_i aibi 的个数就是无解了。
操作过程中要保证 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],aibi此时就从 r r r 操作到 l l l若 ∀ i ∈ [ l , r ] , a i b i \forall i\in[l,r],a_ib_i ∀i∈[l,r],aibi就从 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)。
#includebits/stdc.h
#define ll long long
using namespace std;
constexpr int N1e51;
constexpr ll mod998244353;
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/n1)*(x/n1)*(x%n);
}
struct node
{int num,id;bool operator(const node a)const{return getval(dis[id],num)-getval(dis[id],num1)getval(dis[a.id],a.num)-getval(dis[a.id],a.num1);}
};
priority_queuenode q;
int main()
{freopen(attend.in,r,stdin);freopen(attend.out,w,stdout);cin.tie(0)-sync_with_stdio(0);cinnm;for(int i1;in;i) cina[i];for(int i1;in;i) cinb[i];int fl0;for(int i1;in;i) fl(a[i]!b[i]);if(flm) cout-1,exit(0);for(int i1;in;i){if(a[i]b[i]) continue;dis[i]abs(a[i]-b[i]);q.push({1,i});}if(q.empty()) cout0,exit(0);m-fl;while(m--){node nowq.top();q.pop();now.num;q.push(now);}while(q.size()){ans(ansgetval(dis[q.top().id],q.top().num))%mod;q.pop();}coutans;
}
