国旗计划

链接

这个国家有n个战士,m个边防站,每个战士可以在两个边防站之间奔袭(也就是活动范围)

我们得求对于某个战士,他必须参加的情况下至少需要多少名战士的活动范围覆盖了所有边防站

对于题目的输出样例进行解释 输入:

4 8

2 5

4 7

6 1

7 3

输出: 3 3 4 3

对于第一名战士,他在2-5号边防站,那么还需要第三名还第四名展示才能把所有范围覆盖 也就是3 对于第二名展示,需要第一名和第四名战士,也是3 依次可得答案

由于这个问题涉及一个圆环,但这个圆环只需遍历一次就能遍历完

那么,我们可以把圆环拆成链,并复制一份

当然,还要处理超时问题,一个一个遍历肯定不可能,这题可采用倍增法

这样可减少遍历次数

还有一个问题,就是倍增法的跳格子,这题显然是跳区间,怎么跳呢?

既然要求战士尽可能少,那我们就得使战士覆盖的区间尽可能大,由于战士的区间不能互相包含,那么我们只需要选择尽可能靠右的战士

比如2 5 ||3 6|| 4 8|| 7 9 ,2 5之后我们就应该选择4 8,这样覆盖的区间最大

所以我们还得进行排序

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int LOG = 20;

struct node {
    ll l, r;
    ll idx;
    bool operator<(const node& other)const {
        return l < other.l;
    }
};

int main() {
    ll n, m;
    cin >> n >> m;
    vector<node> soldier(2 * n + 1);
    vector<int> ans(n + 1);

    for (ll i = 1; i <= n; i++) {
        ll l, r;
        cin >> l >> r;
        if (l > r) r += m;
        soldier[i] = { l, r, i };
        soldier[i + n] = { l + m, r + m, i };
    }

    sort(soldier.begin() + 1, soldier.end());

    int total = 2 * n;
    vector<vector<int>> nxt(total + 1, vector<int>(LOG));

    
    int j = 1;
    for (int i = 1; i <= total; i++) {
        while (j <= total && soldier[j].l <= soldier[i].r) {
            j++;
        }
        nxt[i][0] = j - 1;
    }

    for (int k = 1; k < LOG; k++) {
        for (int i = 1; i <= total; i++) {
            nxt[i][k] = nxt[nxt[i][k - 1]][k - 1];
        }
    }


    for (int i = 1; i <= n; i++) {
        int cur = i;  
        int cnt = 1;
        ll target = soldier[i].l + m;

        
        for (int k = LOG - 1; k >= 0; k--) {
            int next_pos = nxt[cur][k];
            if (next_pos != 0 && soldier[next_pos].r < target) {
                cur = next_pos;
                cnt += (1 << k);
            }
        }

        
        cur = nxt[cur][0];
        cnt++;

   
        ans[soldier[i].idx] = cnt;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

时间复杂度:O(N log N)

空间复杂度:O(N log N)