还依稀记得半年前的一次模拟赛，这个题我用暴力拿了50分。 旧题重做，现在来谈谈我的做法。 这种问题有个很套路的转化方式——假定一个答案，然后二分答案。 比如对于假定的答案\(k\)，如果\((i,j) (x_i<x_j)\)连线斜率\(\geq k\)：\[\frac{y_j-y_i}{x_j-x_i} \geq k\]\[y_j-y_i\geq k(x_j - x_i)\]\[y_j-y_i\geq kx_j-kx_i\]\[y_j-kx_j-(y_i-kx_i)\geq0\]\[y_j-kx_j\geq (y_i-kx_i)\] 设\(f(i)=y_i-kx_i\)，则可以变为\(f(i)\leq f(j)\). 结合上面的\(x_i<x_j\)，不难发现就是一个二维偏序：先按\(f\)排序，之后树状数组按\(x\) query即可。
但是我刚开始竟然忘了二维偏序怎么写
/** * @Author: Mingyu Li * @Date: 2019-04-04T17:44:49+08:00 * @Last modified by: Mingyu Li * @Last modified time: 2019-04-04T20:25:23+08:00 */ #include <bits/stdc++.h> #define go(i , x , y) for(register int i = x; i <= y; i++) #define god(i , y , x) for(register int i = y; i >= x; i--) using namespace std; #define ll long long #define fi first #define se second const int N = 100000 + 5; struct Node { ll x, y, rwx, ans; }a[N]; int n,m; ll k; ll b[N] , c[N]; bool cmp(const Node& u, const Node&v) { return u.ans == v.ans ? u.rwx < v.rwx : u.ans < v.ans; } int query(int x) { int ans = 0; for(;x; x -= (x & -x)) ans += c[x]; return ans; } int upd(int x , int val) { for(; x<= m; x += (x & -x)) c[x] += val; } bool check(int mid) { go(i,1,n) a[i].ans = a[i].y - 1ll * mid * a[i].x; sort(a+1,a+n+1,cmp); memset(c,0,sizeof(c)); ll sum = 0; go(i,1,n) { sum += query(a[i].rwx - 1); upd(a[i].rwx , 1); } return sum >= k; } int main() { scanf("%d%lld", &n, &k); go(i,1,n) { scanf("%lld%lld", &a[i].x, &a[i].y); b[i] = a[i].x; } sort(b+1, b+n+1); m = unique(b+1,b+n+1) - (b+1); go(i,1,n) a[i].rwx = lower_bound(b+1,b+m+1,a[i].x) - b; int l = -(int)(2e8), r = (int)(2e8) , ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) ans = mid , l = mid + 1; else r = mid - 1; } cout << ans << endl; return 0; }转载于:https://www.cnblogs.com/LiM-817/p/10887167.html
