牛客2022暑期集训第一场C题 Grab the Seat! 题解

题目大意

二维平面，屏幕是 $(0,1)–(0,m)$ 的线段,有$n$行$m$列座位在屏幕前面，是坐标范围 $1 ≤ x ≤ n, 1 ≤ y ≤ m $的整点。有$k$个座位已经有人，求出到屏幕的视线不被任何人挡住的座位数量。
题目链接
一个人挡住的区域是它与屏幕两端连线所形成的夹角区域。

可见视线遮挡是被两条线段确定的，但是实际上，单条连线也能够确定视线遮挡的范围。,对于一条线，水平向右的直线和它自身形成的夹角，是一定被视线遮挡的，而两条线确定的，刚好就是这两个相邻区域的并集。

对于当前行，能够覆盖该行的，通过左下角的线，一定是在该行以下，而此时显然斜率越大的线，覆盖的越多。
所以我们逐行处理的时候，保存斜率最大的直线。

对于左下角的直线$y=\frac{i-1}{x_{now}}\ast x+1,x=\frac{x_{now}-1}{y-1}$。

$x_{now}$表示斜率最大的线来在第$now$行，且$x$坐标为$x_{now}$。

代码中在分子又额外减一是为了防止结果刚好在整数点上，导致计算错误，因为这个点实际上也是被遮挡的。

右上角的线也同理

我们计算每一行没被覆盖的点。然后计算出左上，左下的线分别的结果。然后取min即可。

代码

#include 
#include 
using namespace std;

const int maxN = 2e5 + 7;

int n, m, k, q, x[maxN], y[maxN], minY[maxN], con[maxN][2];

int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for(int i = 1; i <= k; ++i) 
        scanf("%d%d", &x[i], &y[i]);
    while(q--) {
        int num; scanf("%d", &num);
        scanf("%d%d", &x[num], &y[num]);
        for(int i = 1; i <= m; ++i)
            minY[i] = n + 1;
        for(int i = 1; i <= k; ++i)
            minY[y[i]] = min(minY[y[i]], x[i]);
        int now = 1; con[1][0] = minY[1] - 1;
        for(int i = 2; i <= m; ++i) {
            if((long long) (now - 1) * minY[i] < (long long) (i - 1) * minY[now]) 
                now = i;
            con[i][0] =  ((long long) (i - 1) * minY[now] - 1) / (now - 1);
        }
        now = m; con[m][1] = minY[m] - 1;   
        for(int i = m - 1; i >= 1; --i) {
            if((long long) (m - now) * minY[i] < (long long) (m - i) * minY[now])
                now = i;
            con[i][1] = ((long long) (m - i) * minY[now] - 1) / (m - now);
        }
        long long ans = 0;
        for(int i = 1; i <= m; ++i)
            ans += min(con[i][0], con[i][1]);
        printf("%lld\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39