A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4843: [Neerc2016]Expect to Wait 扫描线 暴力
发表于: | 分类: Oi | 评论:0 | 阅读:228

我们统计每个时刻的时候有多少人在等待

注意我们可以让这个人数是负数,负数的含义就是多了若干本书

然后……?

我们建立直角坐标系,把横坐标当成时间,纵坐标当成是等待的人数

那么询问就是直线,每次就是问一下直线上方的合法的面积了……大力扫描线一下就行了

注意这个扫描线不需要数据结构维护原因是只有一条入边,把询问离线之后记录一下当前的和是多少就行了

无解得特判一下

思路挺好的一道题

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e5+5;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

LL ans[N];
int tot;
int n, q;

struct data {
    int f, x, y;
    data (int _f=0,int _x=0,int _y=0):f(_f),x(_x),y(_y) {}
    bool operator < (const data &z) const {return x < z.x;}
} line[N];

int main() {
//  freopen("tt.in","r",stdin);
    char str[10];
    n = read(), q = read();
    int c = 0;
    int last = 0;
    for(int i=1;i<=n;++i) {
        scanf("%s", str);
        int t = read(), k = read();
        line[++tot] = data(1, c, t - last); last = t;
        if(str[0] == '+') c += k;
        else c -= k;
    }
    for(int i=1;i<=q;++i) {
        int k = read();
        if(-k > c) ans[i] = -1;
        else line[++tot] = data(2, -k, i);
    }
    sort(line+1,line+tot+1);
    line[0].x = line[1].x;
    LL all = 0, temp = 0;
    for(int i=1;i<=tot;++i) {
        all += (LL) temp * (line[i].x - line[i-1].x);
        if(line[i].f == 1) temp += line[i].y;
        else ans[line[i].y] = all;
    }
    for(int i=1;i<=q;++i) {
        if(~ans[i]) printf("%lld\n", ans[i]);
        else puts("INFINITY");
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP