2023牛客寒假算法基础集训营5-D-小沙の赌气

Solost

2023 年 02 月 02 日

287 次浏览

暂无评论

1275字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/02/02/image.png)

## solution

这道题的难点是按照顺序给出区间，然后问你每次能从1到达的位置。

* 错误点有一个地方，我以为是贪心到最远的地方，结果后来发现是不可以调整顺序的
* 正解是把每个区间都放到一个set里面，因为set会自己排序，所以根据pair的第一个值进行排序，然后将每一个区间进行扩展，如果遇到一个元素的首元素小于等于结尾，那就把结尾扩展，注意！！！有一个问题，如果结尾从1开始，那么每个区间的结尾元素得+1，防止定义初始结尾时冲突。例如，刚开始定义`st=1`,给出一个区间是`2-3`，那么这个就不满足情况，因为1是我们初始化的，给出的区间还没给出1，所以不能这样操作，需要将每一个区间扩展的时候将末尾加1，`因为这道题给出的是2解锁了，3也就解锁，不是相交的，可以断开一个`，这要就可以保证初始化的值不会影响正常的区间合并。

---

~~~cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
vector<pair<int, int>> a, b;
set<pair<int, int>> v1, v2;
int ed1 = 1, ed2 = 1;

void op1(){
    while((*v1.begin()).first <= ed1){
        ed1 = max((*v1.begin()).second + 1, ed1);
        v1.erase(v1.begin());
        if(v1.empty()) return;
    }
}

void op2(){
    while((*v2.begin()).first <= ed2){
        ed2 = max((*v2.begin()).second + 1, ed2);
        v2.erase(v2.begin());
        if(v2.empty()) return;
    }
}

int main()
{
    int n;
    cin >> n;
  
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        a.push_back({ l, r });
    }
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        b.push_back({ l, r });
    }
    for (int i = 0; i < n; i++) {
        // if (f1 && a[i].first <= ed1 + 1)
        //     ed1 = max(ed1, a[i].second);
        // if (f2 && b[i].first <= ed2 + 1)
        //     ed2 = max(ed2, b[i].second);
        v1.insert(a[i]);
        v2.insert(b[i]);
        op1();
        op2();
        if (ed1 > ed2) {
            cout << "sa_win!\n";
        } else if (ed1 < ed2) {
            cout << "ya_win!\n";
        } else {
            cout << "win_win!\n";
        }
        cout << abs(ed1 - ed2) << endl;
    }

return 0;
}
~~~

最后修改：2023 年 02 月 02 日