CodeForces 822C Hacker, pack your bags! 【贪心】【模拟】

发表于 | 更新于 | 分类于

题目大意：

给出n个区间，每个区间有个值$c_i​$。现要你从中选出两个区间，使得它们不相交 && 区间长度之和恰好为 x。
无解时输出-1， 存在多个可行解时输出$c_i + c_j​$ 最小的和。

解题思路：

第一感觉是排序后选定一个区间，然后二分找到满足值为$x - c_i$的那个区间，然后写炸了。
后来补题时发现可以用个vector将区间的左端点和值存下来，下标就是区间长度，这样查的时候就变得很好查了。然后每个区间按照左端点从小到大排好序，因为区间长度固定，这样遍历时就可以遍历区间长度为i的区间，对于长度为$x - i$的，只遍历在长度为i的区间的左边的区间并同时记录最小值就可以了。详细看代码吧。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 200010;
const int oo = 2e9+7;

int n, x, l, r, c, res, tem;
vector< pair<int, int> > G[N];

int main()
{
    scanf("%d%d", &n, &x);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d%d%d", &l, &r, &c);
        G[r - l + 1].push_back({l, c});
    }
    for(int i = 1; i < x; ++i)
        sort(G[i].begin(), G[i].end());
    res = oo;
    for(int cost = 1; cost < x; ++cost)
    {
        tem = oo;
        auto &u = G[cost], &v = G[x - cost];
        for(int i = 0, j = 0; i < v.size(); ++i)
        {
            while(j < u.size() && u[j].first + cost - 1 < v[i].first)
            {
                tem = min(tem, u[j].second);
                ++j;
            }
            if(tem != oo)
                res = min(res, tem + v[i].second);
        }
    }
    printf("%d\n", res == oo ? -1 : res);
    return 0;
}
Donate comment here
0%