andyli

题解 CF1213B 【Bad Prices】
题意:计算序列$a$中满足$a_i=min\{a_j, j\in [i,n]\}$的个数。 使用类似滑动窗口的方...
扫描右侧二维码阅读全文
01
2019/09

题解 CF1213B 【Bad Prices】

题意:计算序列$a$中满足$a_i=min\{a_j, j\in [i,n]\}$的个数。
使用类似滑动窗口的方法,每次输入数字时把队列中弹出所有比这个数字大的数,答案就是弹出的次数。注意需要使用优先队列。
代码如下:

#include <cstdio>
#include <queue>
using namespace std;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        priority_queue<int> q;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            while (!q.empty() && x < q.top())
                q.pop(), ans++;
            q.push(x);
        }
        printf("%d\n", ans);
    }
    return 0;
}
Last modification:November 23rd, 2019 at 11:26 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment