Skip to content

14218: 【原4218】睡觉

题目

题目描述

author: flypig 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4218

睡觉

题目描述

同学去军训,要睡大通铺,大通铺里有\(n\)个床位排成一条直线。同学都不安分,有的玩手机,有的斗地主,因而每个床位都有一个整数的吵闹数。对每个床位的同学而言,只要在两侧相距不大于\(d\)的床位中,存在吵闹数大于自己吵闹数两倍的床位,这个床位的同学就会睡不好觉。请问共有多少个床位的同学会睡不好觉。

输入格式

第一行两个整数\(n\), \(d\),表示床位数和影响距离。

接下来\(1\)行,每行\(n\)个正整数,表示了在第\(i\)个床位的吵闹数(数值在整形范围内)。

输出格式

一个正整数,睡不好觉的床位数。

样例输入

8 3
1 3 1 3 5 3 6 7

样例输出

3

数据规模

对于10%的数据有 \(n, k\leq1000\) 对于40%的数据有 \(n, k\leq100000\)
对于100%的数据有 \(n, k\leq2000000\)

yyong119's solution

#include <cstdio>
#define MAX_N 2000020
using namespace std;
struct Node {
    int x, val;
};
int n, k, ans;
int a[MAX_N];
Node sw[MAX_N]; int l, r; // dequeue
bool b[MAX_N];
inline int read() {
    char ch = getchar(); int flag = 1, res = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}

int main() {
    n = read(); k = read();
    for (register int i = 1; i <= n; ++i) a[i] = read();
    // check left side of each number
    l = 0, r = -1;
    for (register int i = 1; i <= n; ++i) {
        while (l <= r && sw[r].val <= a[i]) --r;
        sw[++r].x = i; sw[r].val = a[i];
        if (sw[l].val > (a[i] << 1)) b[i] = true;
        if (i > k && sw[l].x <= i - k) ++l;
    }
    // check right side of each number
    l = 0, r = -1;
    for (register int i = n; i > 0; --i) {
        while (l <= r && sw[r].val <= a[i]) --r;
        sw[++r].x = i; sw[r].val = a[i];
        if (!b[i] && sw[l].val > (a[i] << 1)) b[i] = true;
        if (i <= n - k && sw[l].x >= i + k) ++l;
    }
    for (register int i = 1; i <= n; ++i) ans += b[i];
    printf("%d\n", ans);
    return 0;
}

zqy2018's solution

/*
    Hint: use monotonic queue
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, d, a[5000005];
int que[5000005], hd, tl, que2[5000005], hd2, tl2;
bool is[5000005] = {0};
void init(){
    n = read(), d = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
}
void solve(){
    hd = tl = 0;
    hd2 = tl2 = 0;
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        while(tl > hd && que[hd] < i - d)
            hd++;
        while(tl2 > hd2 && que2[hd2] > (n - i + 1) + d)
            hd2++;
        if(!is[i] && a[que[hd]] > 2 * a[i])
            ans++, is[i] = 1;
        if(!is[n - i + 1] && a[que2[hd2]] > 2 * a[n - i + 1])
            ans++, is[n - i + 1] = 1;
        while(tl > hd && a[que[tl - 1]] <= a[i])
            tl--;
        que[tl++] = i;
        while(tl2 > hd2 && a[que2[tl2 - 1]] <= a[n - i + 1])
            tl2--;
        que2[tl2++] = n - i + 1;
    }
    cout << ans << endl;
}
int main(){
    init();
    solve();
    return 0;
}