第K大斜率
哇哈哈哈哈哈,终于AC了一道紫题
之前这种题即使看题解也不会写,今天是历史性的一步!(写给自己看的)
这题有两个难点
1:斜率怎么转化,求出所有斜率完全不可能,一定会TLE
经过高人指点:我可以利用二分法,先指定一个mid
要求(yj-yi)/(xj-xi)>=mid,由于最终答案向下取整,我们只需要找到至少k个满足题意就行了
证明:设最终答案为s,向下取整得S,此时S=mid,显然s>=mid,比如以下数字,k=1时答案为2
−3,−2,1,3/2,1,2,2/5
满足s>=mid的有2个,由于2和5/2向下取整都是2,所以不会影响答案
如果xj-xi>0,我可以变形得到yj-mid * xj>=yi-mid * xi, 我们令vi=yi-mid * xi
也就是说在我们对x排好序的前提下,只需要找到当j>i时,有多少vj>=vi满足题意
来到卡我最久的一个问题,也就是第二个
2:将问题转化为:
求出一个序列中的满足sj>=si(j>i)的所有(sj,si)对数量,问题也就是前方较小数的计数
比如 2 1 4 2 6 7 3 4
设f(i)为第i个数前面有多少数不大于这个数,f(2)=1,f(4)=2
如果暴力遍历的话也会TLE,因此我们需要别的方法
这个卡了我好久(甚至一度放弃)
但是,我不太甘心,我突然回忆起上次做过的蓝题HH的项链利用的是离线搜索+延迟更新
那么这题可以这么做吗
不妨思考一下,我们对每一个数加一个信息,按这些数字的大小排序后得到的信息
也就是2(2) 1(1) 4(5) 2(3) 6(7) 7(8) 3(4) 4(6)
用差分数组num来看
初始全为0
i=1,num[2]=1(2是这个数字的另外一个信息)
i=2,num[1]=1,num[2]=2(后面记得更新)
i=3,num[5]=3
i=4,num[3]=3,num[5]=4
i=5,num[7]=5
i=6,num[8]=6
i=7,num[4]=4,num[5]=5,num[7]=6,num[8]=7
i=8,num[6]=6,num[7]=7,num[8]=8
那么,f(i)依次是0 0 2 2 4 5 3 5(记得减一因为包含了自己)
为什么可行?原因就在于延迟更新,当我们更新7所对应的数时,由于7后面的3和4没有及时更新,所以此时求和是不包含后面的数字的,这样就保证了答案的正确性
但是,原题还有一个限制,就是x可能相同导致斜率不存在,则不可比较 仔细分析x相同时的特点,我发现x相同v不可能相同,这样我们在排序时只需要x相同时,按v从大到小排序就行
终于得到完整思路,可以用代码实现了(差分数组更新需要树状数组节省时间)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
vector<int>tree;
int n;
struct node {
ll x = 0, y = 0;
int idx = 0;
int index = 0;
ll v = 0;
};
vector<node>num;
int lowbit(int x) {
return x & -x;
}
int query(int x) {
int sum = 0;
for (;x;x -= lowbit(x)) {
sum += tree[x];
}
return sum;
}
void update(int x, int value) {
for (;x <= n;x += lowbit(x)) {
tree[x] += value;
}
}
ll f(ll mid) {
ll sum = 0;
for (int i = 0;i < n;i++) {
num[i].v = num[i].y - mid * num[i].x;
}
sort(num.begin(), num.end(), [](const node& x, const node& y) {
if (x.x == y.x) return x.v > y.v;
return x.x < y.x;
});
for (int i = 0;i < n;i++) {
num[i].idx = i;
}
sort(num.begin(), num.end(), [](const node& x, const node& y) {
if (x.v == y.v) return x.idx < y.idx;
return x.v < y.v;
});
for (int i = 0;i < n;i++) {
num[i].index = i;
}
sort(num.begin(), num.end(), [](const node& x, const node& y) {
if (x.x == y.x) return x.v > y.v;
return x.x < y.x;
});
/*for (int i = 0;i < n;i++) {
cout << num[i].v << " " << num[i].index << endl;
}*/
for (int i = 0;i < n;i++) {
update(num[i].index+1, 1);
/*for (int i = 0;i <= n;i++) {
cout << "tree:" << tree[i] << " ";
}
cout << endl;*/
sum += query(num[i].index+1) - 1;
}
tree.clear();
tree.resize(n + 1, 0);
return sum;
}
int main() {
ll k;
cin >> n >> k;
tree.resize(n + 1, 0);
num.resize(n);
for (int i = 0;i < n;i++) {
cin >> num[i].x >> num[i].y;
}
ll left = -200000000, right = 200000000;
ll ans = 0;
while (left <= right) {
ll mid = (right + left) / 2;
ll K = f(mid);
/*cout <<"K:"<< K << endl;
cout <<"mid:"<< mid << endl;*/
if (K >= k) {
ans = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
/*cout << f(2) << endl;
cout << f(3) << endl;
cout << f(1) << endl;
cout << f(0) << endl;
cout << f(-1) << endl;
cout << f(-2) << endl;
cout << f(-3) << endl;*/
cout << ans;
}
不必在意注释,调试结果而已
时间复杂度:O(nlog n)
空间复杂度:O(n)