首先，因为士兵是环形的，所以先将其拆分为链，并且每个士兵的移动位子不会被包含，所以只需要对左端点进行排序就能得到一个递增的区间
点击查看代码
void init()
{cin >> n >> m;int i;for (i = 1; i <= n; ++i){w[i].i1 = i;cin >> w[i].l >> w[i].r;if (w[i].r < w[i].l)//如果右端点小于左端点，加上m，让成为链的时候右端点在左端点的右边w[i].r += m;}sort(w + 1, w + n + 1);//根据左端点进行排序n2 = n * 2;i = n + 1;for (i; i <= n2; i++)//复制一份{w[i].i1 = w[i - n].i1;w[i].l = w[i - n].l + m;w[i].r = w[i - n].r + m;}
}
之后如此图，
如果a是一点要选的话，那么根据贪心，下一个选择最好的方案就是c，也就是在左端点小于当前右端点的情况下，右端点最远的点，此时我们假设a(f,j)为战士在f点跑2的j次方到达的边防站，那就可以转化为a（a(f,j-1),j-1）到达的边防站，（2的n次方=2的（n-1）次方*2）因为 2的20次方为1000000，够用了，所以我们以此预处理每组数据
点击查看代码
void st()
{int o = 1;for (int i = 1; i <= n2; ++i){while (o <= n2 && w[o].l <= w[i].r)o++;a[i][0] = o - 1; // 找到左端点小于当前i的右端点且右端点最远的点}for (int i = 1; (1 << i) <= n; ++i)//i相当于从s点走了2的i次{for (int s = 1; s <= n2; ++s){a[s][i] = a[a[s][i - 1]][i - 1];//公式}}
}
点击查看代码
/* 台州第一深情 */
#include <iostream> // 输入输出流
#include <iomanip> // 输入输出格式控制
#include <fstream> // 文件输入输出流
#include <sstream> // 字符串输入输出流
#include <cmath> // 数学函数
#include <string> // 字符串操作
#include <vector> // 动态数组容器
#include <queue> // 队列容器
#include <stack> // 栈容器
#include <set> // 集合容器
#include <map> // 映射容器
#include <unordered_set> // 无序集合容器
#include <unordered_map> // 无序映射容器
#include <algorithm> // 算法
#include <bitset> // 位集容器
#include <stdio.h> // 标准输入输出
using namespace std;
using i64 = long;
// using int = long long;
typedef pair<int, int> PII;
const int N = 4e5 + 10;
int n1;
struct vv
{int i1, l, r;bool operator<(const vv &b) const { return l < b.l; }
} w[2 * N]; // 将环形记录成链
int a[N][25];
int res[N];
int n, m, n2;void init()
{cin >> n >> m;int i;for (i = 1; i <= n; ++i){w[i].i1 = i;cin >> w[i].l >> w[i].r;if (w[i].r < w[i].l) // 如果右端点小于左端点，加上m，让成为链的时候右端点在左端点的右边w[i].r += m;}sort(w + 1, w + n + 1); // 根据左端点进行排序n2 = n * 2;i = n + 1;for (i; i <= n2; i++)//复制一份{w[i].i1 = w[i - n].i1;w[i].l = w[i - n].l + m;w[i].r = w[i - n].r + m;}
}void st()
{int o = 1;for (int i = 1; i <= n2; ++i){while (o <= n2 && w[o].l <= w[i].r)o++;a[i][0] = o - 1; // 找到左端点小于当前i的右端点且右端点最远的点}for (int i = 1; (1 << i) <= n; ++i) // i相当于从s点走了2的i次{for (int s = 1; s <= n2; ++s){a[s][i] = a[a[s][i - 1]][i - 1]; // 公式}}
}
void solve(int x)
{int len = w[x].l + m, now = x, ans = 1;//len就是计划点for (int i = 20; i >= 0; --i){int to = a[now][i];//如果当前点走2的i次方步存在最优点，那下一个i判断的就是从当前最优点开始走2的i次方步能否到达下一个最优点，一直到计划点if (to && w[to].r < len){ans = ans + (1 << i);now = to;}}res[w[x].i1] = ans + 1;//只能加上最后一个点，如果加其他数那都证明for循环每盘玩，因为if的判断条件是小于计划点
}
int main()
{init();st();for (int i = 1; i <= n; ++i){solve(i);}for (int i = 1; i <= n; ++i){cout << res[i] << " \n"[i == n];}return 0;
}
}
