网站策划案需要包括哪些,品牌咨询,条码生成器,个体营业执照网上申请登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;给出一个n个数的数组a#xff0c;求一个排列#xff0c;使其形成的其中一个置换环上的数的和k#xff0c;并使产生的逆序对数量最少
1n1e3;-1e6k1e6;-1e6ai1e6
tips:关于置换环是什…登录—专业IT笔试面试备考平台_牛客网
题目大意给出一个n个数的数组a求一个排列使其形成的其中一个置换环上的数的和k并使产生的逆序对数量最少
1n1e3;-1e6k1e6;-1e6ai1e6
tips:关于置换环是什么可以看这道经典题D. Lucky Permutation codeforces1768D_timidcatt的博客-CSDN博客
思路一个置换环内产生的逆序对最少为n-1例如在n4时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
#includebits/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_queueintout;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;
}
