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

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;
}

http://www.lryc.cn/news/112235.html

相关文章:

  • VC9、VC10、VC11等等各对应什么版本的Visual Studio,以及含义
  • 两数相加 LeetCode热题100
  • Python基础 P2数字类型与优先级进阶练习
  • CAPL通过继电器实现CAN容错性自动化测试
  • elasticsearch 配置用户名和密码
  • 侯捷 C++面向对象编程笔记——9 复合 委托
  • 状态模式——对象状态及其转换
  • Linux一阶段复习
  • 宝塔Linux面板怎么升级?升级命令及失败解决方法
  • 前端面试的性能优化部分(6)每天10个小知识点
  • 2023年 Java 面试八股文(20w字)
  • 银河麒麟服务器ky10-server在线一键安装docker
  • spring boot中web容器配置
  • DNSlog注入(利用DNSlog平台将SQL盲注变成回显注入)
  • vim学习笔记(致敬vim作者)
  • 力扣 -- 139. 单词拆分
  • 百度秋招攻略,百度网申笔试面试详解
  • nohup Java -jar 生成的nohup.out 文件一直增加,如何处理
  • 静态页面与动态页面的区别及部署jpress应用
  • 华为数通HCIA-华为VRP系统基础
  • 基于Azure OpenAI Service 的知识库搭建实验⼿册
  • 第七节--结构体
  • Docker学习(二十四)报错速查手册
  • 一种SpringBoot下Scheduler定时任务优雅退出方案
  • DNS部署与安全详解(上)
  • 【51单片机】晨启科技,酷黑版,音乐播放器
  • 基于SPSSPRO实现层次分析法(AHP)
  • Spring Test中使用MockMvc进行上传文件单元测试时,报NullPointerException
  • HTTP常用状态码及其含义
  • FFmpeg中AVIOContext的使用