【三中校内训练】怎样更有力气

【问题描述】

OI大师抖儿在夺得银牌之后，顺利保送pku。这一天，抖儿问长者：“我虽然已经保送了，但我的志向是为国家健康工作五十年。请问我应该怎样变得更有力气？”
长者回答：“你啊，Too Young Too Simple,Sometimes Naive!如果你想要我教你，你要先进行艰苦的修行。”

长者的住宅中有一堵长度为n的墙。每天抖儿起床修行，会选择一段长度为x的区间染成白色。长者的住宅附近有一群香港记者，为了借助抖儿拜访长者，第i天香港记者会将区间[l_i,r_i]染成白色来讨好抖儿（也就是说，每天墙会被抖儿和香港记者各染一次）。现在抖儿已经预先知道了香港记者的动向，他想知道他最少几天就能把墙全部染白，完成修行。

【输入格式】

第一行三个整数n,m,x，分别表示墙的长度，天数和区间的长度。

接下来m行，每行两个整数l_i、r_i，表示香港记者在第i天会将区间[l_i,r_i]染成白色。

【输出格式】

一行一个整数，表示抖儿最少几天能把墙全部染白。

如果m天之后依然无法染白，则输出“Poor Douer!”

【输入样例1】

10 3 3

2 5

4 8

9 10

【输出样例1】

【样例1说明】

第一天抖儿刷墙的区间为[1,3]

第二天抖儿刷墙的区间为[8,10]

【输入输出样例2】

见选手目录下的liqi/liqi2.in和liqi/liqi2.out

【限制与约定】

对于所有的数据，保证n≤10¹⁸，m≤100000，x≤n且数据随机

二分答案，之后按左端点排序，统计+x的次数

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define il inline
#define re register
#define ceil(a) ((a)==int(a))?a:(int(a)+1)
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=100010;
struct data{ll l,r;int pos;} a[N],c[N];
int m,tot;ll n,x;
il bool cmp(re data a,re data b){
    if(a.l!=b.l) return a.l<b.l;
    return a.r<b.r;
}
il ll read(){
    re ll hs=0;re char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){
        hs=(hs<<3)+(hs<<1)+c-'0';
        c=getchar();
    }
    return hs;
}
il bool chk(int k){
    re ll ans=0,cover=0,t;tot=0;
    for(re int i=1;i<=m;i++) 
        (a[i].pos<=k)?(c[++tot]=a[i],1):0;
    for(re int i=1;i<=k;i++){
        if(c[i].l<=cover+1) cover=max(cover,c[i].r);
        else{
            if(!x) return false;
            t=ceil(double(c[i].l-cover-1)/x);
            ans+=t;cover+=t*x;
            cover=max(cover,c[i].r);
        }
    }
    if(cover<n) ans+=ceil(double(n-cover)/x);
    return ans<=k;
}
int main(){
    freopen("liqi.in","r",stdin);
    freopen("liqi.out","w",stdout);
    n=read();m=read();x=read();
    for(int i=1;i<=m;i++){
        a[i].l=read();a[i].r=read();a[i].pos=i;
    }
    sort(a+1,a+m+1,cmp); 
    if(!chk(m)){cout<<"Poor Douer!";return 0;}
    int l=1,r=m,mid;
    while(l<r){
        mid=(l+r)/2;
        if(chk(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}