K - Two Contests
2024-09-06 04:32:40
题目连接:https://atcoder.jp/contests/agc040/tasks/agc040_b
大佬题解:https://blog.csdn.net/duanghaha/article/details/102892233
题意:有N个问题,每个问题可以由编号L~R之间的人完成,有两个集合S和T,将N个问题放入两个集合中,使得交集和最大
题解与证明
首先找到lmost,与rmin,当区间rmin与lmost在同一个集合中,此时答案为rmin-lmost+1+most_width(最大宽度)
当二者不再同一个集合中时,那么答案为 max((rmin-x+1)+(y-lmost+1))其中x为l[i],y为r[j]注意x与y不可以是同一个区间的左右边界。
现在已经确定了集合S中有lmost,所以,T中一定有rmin。。问题转换为一个数组,,两个参数,将这个数组划分为来年部分。使得两部分的和最大
ACcode
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+;
const int N=1E5+;
int l[N],r[N];
int arr[N];
struct stu{
int a,b;
bool friend operator <(const stu &x,const stu &y){
return x.a>y.a;
}
}s[N];
int main()
{
int n;
cin>>n;
int lmax=,rmin=INF,width=;
for(int i=;i<=n;i++){
cin>>l[i]>>r[i];
if(l[i]>=lmax) lmax=l[i];
if(r[i]<=rmin) rmin=r[i];
width=max(width,r[i]-l[i]+);
}
int sum=max(rmin-lmax+,)+width;
for(int i=;i<=n;i++){
s[i].a=max(,rmin-l[i]+);
s[i].b=max(,r[i]-lmax+);
}
sort(s+,s++n);
arr[n]=s[n].b;
for(int i=n-;i>=;i--) arr[i]=min(arr[i+],s[i].b);
int ans=;
for(int i=;i<=n-;i++) ans=max(ans,s[i].a+arr[i+]);
cout<<max(ans,sum)<<endl;
return ;
}
最新文章
- YUM源的简介,配置与使用
- 三星在GPL下发布其exFAT文件系统实现源码
- 替换空格-请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
- 【CSS】最全的CSS浏览器兼容问题
- 软件包 java.util 的分层结构
- 多目标遗传算法 ------ NSGA-II (部分源码解析) 临时种群生成新父代种群 fillnds.c
- ACM2036_改革春风吹满地(多边形面积计算公式)
- Ueditor文本编辑器(新浪SAE平台版本) - 下载频道 - CSDN.NET
- IoC容器Autofac正篇之类型注册(五)
- JavaScript 再谈闭包
- Java基础之 反射是什么?
- mybatis:自动分页插件
- 详解webpack中的hash、chunkhash、contenthash区别
- HttpLuaModule——翻译(Nginx API for Lua)
- Tomcat 的 DefaultServlet
- adc转换原理
- dubbo监控中心搭建
- java反射中的动态代理机制(有实例)
- python-python爬取豆果网(菜谱信息)
- Java枚举类型的用法