ZRoi-rectangle题解

· · 个人记录

题面

Zbox在一个画图板上随便画了一些点, 现在他玩腻了, 于是想擦掉它们.

这个画图板的橡皮擦非常奇怪, 橡皮擦是一个矩形, Zbox只能指定橡皮擦的长宽但无法改变它的面积.

更奇怪的是, 橡皮擦的左上角必须被放在图片的左上角(也就是坐标(0,0)的位置, 这取决于你怎么看这个坐标, 所有点的坐标都是非负的).

这样看来, Zbox并没有办法一次擦掉所有的点了, 他想知道他一次最多能够擦掉多少个点.

思路1

这道题应该是数学+几何题，感觉应该是蓝题难度

我们把黑板看作是一个平面直角坐标系，上面有一些点，如图：

这个橡皮擦的左下角是被固定的，也就是(0,0)点，随着长的变化，宽也会变化，设长为x，宽为y，面积为S，则:

y=\frac{S}{x}

那么黑板擦的右上角就可以形成一个反比例函数，如图：

那么问题就转化为：在反比例函数上选一个点，将其作为矩形的右上角，原点作为左下角，使矩形里的点数量最多。

我们想一下，以E点为例，它能对函数上的那一段区间产生贡献（也就是在右上角在哪一个区间里能把该点擦掉），很显然，画一下图：

E点能产生贡献的区间就是F到H之间，假设E点的坐标为(x,y)，那么F的坐标就是(x,\frac kx)，H点的坐标就是(\frac ky,y)

把所有的点能产生贡献的区间都算出来，如果点的个数为n，那么我们就能得到n个区间。但是它们是二维的，我们就给它们降维打击，得到了许多区间，我们求的就是重叠区间最多的重叠数

n个区间，2n个点，我们把这些点进行离散化，暴力枚举即可

思路2

这个思路就比较难了

感性理解一下，我们橡皮擦的右上角的x坐标肯定是n个点中的一个，因为如果多了一点也不会多擦一个点，这就很贪心

我们用一个树状数组或线段树来维护一个与y轴平行、从左往右移动的扫描线，就完了，

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <cmath>
#include <cstring>
#include <string>
#include <memory.h>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <ctime>
using namespace std;
typedef long long ll;
ll n,S,m;
struct cord{
    ll x,y;
}a[500010];
ll s[500010];
ll lowbit(ll x){return x&(-x);}
void update(ll x,ll k)
{
    for(ll i=x;i<=m;i+=lowbit(i))
    {
        s[i]+=k;
    }
}
ll query(ll x)
{
    ll ret=0;
    for(ll i=x;i;i-=lowbit(i)) ret+=s[i];
    return ret;
}
bool cmp(cord x,cord y)
{
    return x.x==y.x?x.y<y.y:x.x<y.x;
}
int main()
{
    scanf("%lld%lld",&n,&S);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld%lld",&a[i].x,&a[i].y);
        m=max(m,a[i].y);
    }
    sort(a+1,a+1+n,cmp);
    ll ans=0xcfcfcfcfcfcfcfcf;
    for(ll i=1;i<=n;i++)
    {
        update(a[i].y,1);
        ans=max(ans,query(min(m,S/a[i].x)));
    }
    printf("%lld",ans);
    return 0;
}