[POI2013]Taksówki

题目大意：

ABC三地在同一条直线上，AC相距\(m(m\le10^{18})\)米，AB相距\(d\)，B在AC之间。总共有\(n(n\le5\times10^5)\)辆车，每辆车只能从B地出发开\(x_i\)米（开完以后不必把车开回B地），问从A到C至少要坐几辆车？

思路：

对于BC之间的那一段路，如果可以走，则只要坐一辆车。对于AB之间的情况，只需要从大到小贪心即可。

将\(x\)排序后，找到大于等于\(m-d\)的最小的\(x_i\)，作为从B到C的车，剩下的车用来贪心。

时间复杂度\(\mathcal O(n\log n)\)。

源代码：

#include
    
     #include
     
      #include
      
       #include
       
        typedef long long int64;inline int64 getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int64 x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=5e5;int64 x[N];int main() {    const int64 m=getint(),d=getint();    const int n=getint();    for(register int i=0;i
        
         ());    if(x[0]
         
          =m-d;k++); int64 p; for(p=i=0;i
          
           
            =d-p;i++) { if(i!=k) p+=x[i]-d+p; } if(i<=k) i++; if(p>=m) { printf("%d\n",i-1); return 0; } printf("%d\n",p+x[k]-std::max(d-p,0ll)>=m?i:0); return 0;}