当前位置：首页 > news >正文

E. 23 Kingdom【Codeforces Round 1024 (Div. 2)】

news 来源：原创 2025/7/4 16:29:07

E. 23 Kingdom

思路：

这道题的核心在于如何构造一个数组b，使得每个数的最远两个出现位置之差总和最大。通过分析，我们发现要最大化总美丽值，应尽可能让每个数的首次出现尽可能靠左、末次出现尽可能靠右。这样每个数的距离贡献j-i会尽可能大。

为了实现这一点，采用贪心策略：双指针从左右两端向中间扫描，每次尝试为当前左指针位置的数a[l]寻找一个右端的配对a[r]。若这两个位置的数值在各自的可用范围内未被使用过，则将它们的间距r-l累加到答案中，并标记这些位置已被使用。重复此过程直到所有可能的配对被处理完毕。

具体实现中，使用并查集（路径压缩优化）来高效管理每个数值的可用左右端点。bookl数组记录每个数值当前可用的最左端点（初始为自身位置），当该位置被使用后，更新为前一个位置。同理，bookr数组记录每个数值当前可用的最右端点。每次配对成功时，更新相应的并查集结构，确保后续查找能快速找到下一个可用端点。

这种贪心策略确保了每次选择的配对间距尽可能大，从而总和达到最大。通过并查集的高效管理，算法的时间复杂度为线性，适用于大规模数据。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
#define FU(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FD(i, a, b) for(int i = (a); i >= (b); -- i)
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int maxn= 5e5+5,MAXN = maxn;
int a[200005],b[200005],c[200005];
int bookl[200005],bookr[200005];
int find(int x,int book[]){if(x==book[x]) return x;return book[x] = find(book[x],book);
}void solve() {int n;cin>>n;int ans=0,l=1,r=n;for(int i=1;i<=n;i++){cin>>a[i];bookl[i]=bookr[i]=i;}while(l<r){while(l<r&&find(a[l],bookl)==0) l++;while(l<r&&find(a[r],bookr)==0) r--;if(l<r){ans+=r-l;int lt=find(a[l],bookl),rt=find(a[r],bookr);bookl[lt]=lt-1;bookr[rt]=rt-1;l++,r--;}}cout<<ans<<endl;
}	signed main() {
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifcin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

思路：

代码：

相关文章：