Circle of Mistery 2023牛客暑期多校训练营5 B

登录—专业IT笔试面试备考平台_牛客网

题目大意：给出一个n个数的数组a，求一个排列，使其形成的其中一个置换环上的数的和>=k，并使产生的逆序对数量最少

1<=n<=1e3;-1e6<=k<=1e6;-1e6<=ai<=1e6

tips:关于置换环是什么可以看这道经典题D. Lucky Permutation codeforces1768D_timidcatt的博客-CSDN博客

思路：一个置换环内产生的逆序对最少为n-1，例如在n=4时，2,3,4,1构成的置换环。首先，如果数组中有大于>=k的数，答案肯定是0，所以在k小于等于0时，有答案的充要条件也就是存在a[i]>=k。

然后因为数组中有负数，而要想和>=k，肯定要选正数，那么我们选择的正数之间肯定还会夹杂负数，为了尽量产生少的影响，所以要保持p[i]=i（因为递增数组的逆序对数量为0，每交换一对相邻数，都会使逆序对数量改变1），那么就会产生如2,5,6,3,4,1这样的置换环排列置换环部分也就是2,5,6,1这部分产生的贡献就是环的大小-1,中间的3,4分别会与环最右边的数，和左边环中第一个数产生一个逆序对，所以中间不在环中的每一个数贡献都是2，所以对于一个满足要求的区间，它的答案即为（区间长度-环的大小）*2+环的大小-1=区间长度*2-换的大小

然后我们找这样的区间，可以贪心一下，我们从上面的式子可以看出，要想答案最小，就要找一个最短的区间，并且使里面的环的大小最大。

要找一个最短的区间，显然需要区间端点都是正数，可以用尺取的方式找到这样的一个区间，要是区间里的环最大，区间里的大于等于0的数肯定都选，负数就要用一个大根堆存起来，在找到合法区间后，尽可能加上大的负数，这样就能使得答案最小

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
const int INF = 0x7fffffff;
const ll MOD = 998244353;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;t = 1;while (t--){int n, k;cin >> n >> k;bool flag = 0;for (int i = 1; i <= n; i++){cin >> a[i];if (a[i] >= k)flag = 1;//先特判逆序对数量为0的情况}if (flag){cout << 0 << endl;return 0;}int ans = INF;for (int i = 1; i <= n; i++){if (a[i] <= 0)continue;//找到一个正数作为区间左端点int cnt = 0;int sum = 0;priority_queue<int>out;for (int j = i; j <= n; j++){if (a[j] >= 0){//正数都选进环里sum += a[j];cnt++;//记录环的大小}else{out.push(a[j]);//记录区间内的负数}if (sum < k)continue;//找一个和>=k的区间                 while (!out.empty() && sum + out.top() >= k){//尽可能的选更多的负数int temp = out.top();sum += temp;out.pop();cnt++;}ans = min(ans, (j - i + 1 - cnt) * 2 + cnt - 1);//维护答案最小值break;//继续去找下一个区间                }}if (ans == INF){cout << -1 << endl;}elsecout << ans << endl;}return 0;
}