題意
https://vjudge.net/problem/CodeForces-1257E
三個人，每個人有一些數字，組合起來是1~n，每個人可以給另一個人一個擁有的數字，問最小運算元，使得第一個人擁有1~i的數，第二個人擁有i+1~j的數，第三個人擁有j+1~n的數，即第一個人為前綴，第二個人為中間部分，第三個人為后綴， 注意：可以有一個或兩個人最后不擁有數字，
思路
先把問題簡單化，考慮只有兩個人的情況，設cnt1[x]表示第一個人前x個數擁有的個數，cnt2[x]表示第二個人前x個數擁有的個數，如果第一個人獲得的前綴為1~i，第二個人獲得的后綴為i+1~n，那么代價為cnt2[i]+cnt1[n]-cnt1[i]，
再考慮三個人的情況，同樣，如果第一個人獲得1~i，第二個人獲得i+1~j，第三個人獲得j+1~n，那么代價為cnt2[i]+cnt3[i] +cnt1[j]-cnt1[i]+cnt3[j]-cnt3[i] + cnt1[n]-cnt1[j]+cnt2[n]-cnt2[j]，化簡得：cnt2[i]-cnt1[i]+cnt3[j]+cnt1[n]+cnt2[n]-cnt2[j]，即cnt2[i]-cnt1[i] + cnt1[n]+cnt2[n] + cnt3[j]-cnt2[j]，所以列舉i，使這個式子值最小，發現還剩下兩個和j有關的項對式子有影響，而j>=i，于是問題轉化成了列舉i，求cnt2[i]-cnt1[i]+min(cnt3[i~n]-cnt2[i~n])+cnt1[n]+cnt2[n]，我們只用維護cnt3[j]-cnt2[j]的后綴最小值即可，
注意：因為可能有一個人或兩個人沒有任何數，那么此時i和j是可以相等的，比如i==j時第二個人沒有數，i==j==0時第1、2個人沒有數，i==j==n時第二、三個人沒有數，i==0&&j==n時第1、3個人沒有數，等等情況
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int a[4][N];
int c[4][N],mn[N];
int main()
{
std::ios::sync_with_stdio(false);
int k1,k2,k3;
cin>>k1>>k2>>k3;
int n=k1+k2+k3;
for(int i=1;i<=k1;i++)
{
cin>>a[1][i];
++c[1][a[1][i]];
}
for(int i=1;i<=k2;i++)
{
cin>>a[2][i];
++c[2][a[2][i]];
}
for(int i=1;i<=k3;i++)
{
cin>>a[3][i];
++c[3][a[3][i]];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++)
{
c[j][i]+=c[j][i-1];
}
}
mn[n+1]=inf;
for(int i=n;i>=0;i--)
{
mn[i]=min(mn[i+1],c[3][i]-c[2][i]);
}
int ans=inf;
for(int i=0;i<=n;i++)
{
ans=min(ans,c[2][i]-c[1][i]+mn[i]+c[1][n]+c[2][n]);
// cout<<i<<" "<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/122723.html
標籤：其他