国旗计划

倍增

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+1;
int n, m;
struct warrior{
  int id, L, R;                                                 //id:战士的编号；L、R，战士的左右区间
  bool operator < (const warrior b) const{return L < b.L;}      //重载<操作符。可以对两个node使用<操作符进行比较
}w[N*2];
int n2;
int go[N][20];
void init(){                                                    //贪心 + 预计算倍增
  int nxt = 1;
  for(int i=1;i<=n2;i++){                                       //用贪心求每个区间的下一个区间
    while(nxt<=n2 && w[nxt].L<=w[i].R)
      nxt++;                                                    //每个区间的下一个是右端点最大的那个区间
    go[i][0] = nxt-1;                                           //区间i的下一个衔接区间
  }
  for(int i=1;(1<<i)<=n;++i)                                    //倍增：i=1,2,4,8,... 共log(n)次：4人for循环两次
    for(int s=1;s<=n2;s++)                                      //每个区间后的第2^i个区间
      go[s][i] = go[go[s][i-1]][i-1];                           //go[战士id][战士接力次数]：i的长度看战士的接力棒有几个
}
int res[N];
void getans(int x){                                             //从第x个战士出发
  int len=w[x].L+m, cur=x, ans=1;                               //ans=1是加上第一棒接力战士
  for(int i=log2(N);i>=0;i--){                                  //从最大的i开始找：2^i = N
    int pos = go[cur][i];                                       //pos：战士的下一棒给谁
    if(pos && w[pos].R < len){                                  //战士的下一棒不超出m的长度
      ans += 1<<i;                                              //累加跳过的区
      cur = pos;                                                //从新位置继续开始
    }
  }
  res[w[x].id] = ans+1;                                         //加上收尾的最后一棒
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
    w[i].id = i;                                                //记录战士的顺序
    scanf("%d%d",&w[i].L, &w[i].R);
    if(w[i].R < w[i].L) w[i].R += m;                            //把环变成链：右端的数据跑回起点，加上总长
  }
  sort(w+1, w+n+1);                                             //按左端点排序
  n2 = n;
  for(int i=1;i<=n;i++)                                         //拆环加倍成一条链
  { n2++; w[n2]=w[i]; w[n2].L=w[i].L+m; w[n2].R=w[i].R+m; }     //翻一倍，覆盖R+m的范围
  init();
  for(int i=1;i<=n;i++) getans(i);                              //逐个计算每个战士
  for(int i=1;i<=n;i++) printf("%d ",res[i]);
  return 0;
}

笔记：这个题目要求是战士覆盖了所有的边防站，倍增跟二分法一样都是为了查找单调数据组中的某一数值。二分法是分割，倍增是跳跃，每次的跳跃的距离随着接近目标慢慢变小，直到差最后一步就直接跳过去，逻辑有点类似有点类似“芝诺悖论”