Codeforces Round 879 (Div. 2) D题 记录做法

首先给出题目来源
Codeforces Round 879 (Div. 2) D题

先通读一遍题目，我们可以知道本题的思路就是要求2个区间的最大不重合区间，以此来让一个人的分数尽可能高一个人的分数尽可能低。
我们第一反应就是n方的暴力做法但看一眼数据范围是2e5，当然暴力的做法就废了（废话。。。我就没见过d题还能暴力写的）。
本题我的思路类似于贪心，将每个区间可能遇到的情况分成3种：

	1、存在有区间的右端点在此区间内，左端点不在：重合区间大小为 minr - a[i].l + 1再对是否右端点也不在进行特判-->  重合区间大小为0 2、存在有区间的左端点在此区间内，右端点不在：重合区间大小为 a[i].r - maxl + 1再对是否左端点也不在进行特判-->  重合区间大小为0 3、存在有区间被此区间完全包含-->此时直接用最小的区间长度 minlen 就好不管是不是这个最小区间，最后不可能再比这个最小区间重合的少解释：（1）如果不完全包括这个最小区间，则在上两种情况就已经判断出是重合区域是0还是一部分的这个最小区间，此时已经得到了比minlen更小的区域，再与minlen比较也不会改变结果。（2）如果完全包括了这个最小区间，那么上面两种情况就都多了一部分左侧未重合或右侧未重合，此时再与minlen比较才能得出正确的重合区间。（3）只需要判断最小区间是贪心的思想，仔细想想就可以发现判断其他更大的区间肯定不会有判断最小区间优。

至此本题的关键点已经解释完毕，代码细节详见注释，如果要是哪里有错误的话，欢迎大佬指正（轻喷求求了 qaq ）

#include
#include
using namespace std;
#define ll long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define PII pair<int,int>
//#define int long longconst int N = 1e5 + 5;inline int min(int aa, int bb, int cc) {return aa < bb ? (aa < cc ? aa : cc) : (bb < cc ? bb : cc);
}
struct zcx {int l, r;
};
zcx a[N];void solve() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i].l >> a[i].r;}int maxl = 0, minr = INF, minlen = INF;for (int i = 1; i <= n; i++) {maxl = max(maxl, a[i].l);   //最大左侧边minr = min(minr, a[i].r);   //最小右侧边minlen = min(minlen, a[i].r - a[i].l + 1);  //最小区间}int ans = 0;for (int i = 1; i <= n; i++) {//分别对每个区间进行枚举int z1 = max(minr - a[i].l + 1, 0);//存在区间右端点在此区间内（同样包含右端点小的甚至比此区间左端点还小的情况：0）int z2 = max(a[i].r - maxl + 1, 0);//同上（不过是判断左端点）int zz = min(z1, z2, minlen);   //zz是表示我们要求的最小重合区间ans = max(ans, a[i].r - a[i].l + 1 - zz);//此区间长度减去zz，求最大不重合区间}cout << ans * 2 << endl;//一人加一，一人减一，差值为2倍
}signed main() {int tt;cin >> tt;while (tt--) {solve();}return 0;
}

运行结果：

结束！撒花！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！