题目大意

给出一个数字序列，要求将这个数字序列变成单调不降的序列。若原来的数字是A[i],变化之后的数字是B[i],那么花费是 |A[i]?B[i]| 。求出一种方案，使得最大的花费最小。

思路

一眼就能看出是二分，然后贪心什么的随便yy一下就行了。

CODE

#define _CRT_SECURE_NO_WARNINGS

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MAX 50010 using namespace std; #define LEFT (pos << 1) #define RIGHT (pos << 1|1) struct Cow{ int x,y,c; int st,ed; bool operator <(const Cow &a)const { return y > a.y; } void Read() { scanf("%d%d%d", &x, &y, &c); x *= -1; st = c * (x - 1); ed = st + (c << 1); } }src[MAX]; int cows; pair
       
         xx[MAX << 1]; int cnt,t; int tree[MAX << 4]; inline void PushDown(int pos) { if(tree[pos]) { tree[LEFT] = tree[pos]; tree[RIGHT] = tree[pos]; tree[pos] = 0; } } void Modify(int l, int r, int x, int y, int c, int pos) { if(l == x && y == r) { tree[pos] = c; return ; } PushDown(pos); int mid = (l + r) >> 1; if(y <= mid) Modify(l, mid, x, y, c, LEFT); else if(x > mid) Modify(mid + 1, r, x, y, c, RIGHT); else { Modify(l, mid, x, mid, c, LEFT); Modify(mid + 1, r, mid + 1, y, c, RIGHT); } } inline int Ask(int l, int r, int x, int pos) { if(l == r) return tree[pos]; PushDown(pos); int mid = (l + r) >> 1; if(x <= mid) return Ask(l, mid, x, LEFT); return Ask(mid + 1, r, x, RIGHT); } bool v[MAX]; int main() { cin >> cows; for(int i = 1; i <= cows; ++i) src[i].Read(); sort(src + 1, src + cows + 1); for(int i = 1; i <= cows; ++i) { xx[++cnt] = make_pair(src[i].st, &src[i].st); xx[++cnt] = make_pair(src[i].ed, &src[i].ed); } sort(xx + 1, xx + cnt + 1); for(int i = 1; i <= cnt; ++i) { if(i == 1 || xx[i].first != xx[i - 1].first) ++t; *xx[i].second = t; } for(int i = 1; i <= cows; ++i) Modify(1, cnt, src[i].st, src[i].ed , i, 1); for(int i = 1; i <= cnt; ++i) v[Ask(1, cnt, i, 1)] = true; int ans = 0; for(int i = 1; i <= cows; ++i) ans += v[i]; cout << ans << endl; return 0; }