ICPC 2018 南京网络预赛 G Lpl and Energy-saving Lamps

【题目链接】

题目意思

第一行给两个整数n m，n表示房间数，m表示每个月购买的的灯泡数，随后给出n个数，表示每个房间的灯泡数（每个灯泡只需要更换一次），每个月从第一个房间遍历到第n个房间，当该房间的灯泡数小于等于现在有的灯泡数时，更新该房间的灯泡（只更新一次）。
然后给出q次询问，问你在某一个月时，已经更换灯泡的房间数和现在剩余的灯泡。（当所有房间灯泡都更换后，不再买入新的灯泡。）

样例输入
5 4
3 10 5 2 7
10
5 1 4 8 7 2 3 6 4 7
样例输出
4 0
1 1
3 6
5 1
5 1
2 0
3 2
4 4
3 6
5 1

解题思路

线段树维护区间最小值，当总区间的最小值大于当前灯泡数就进入下一个灯泡，否则一直寻找小于当前灯泡的最前面的数字。

AC代码

#include <iostream>
#include <algorithm>
#include <climits>
using ll = long long;
using namespace std;
struct node
{
    int l;
    int r;
    ll min;
}que[200005];
struct Node
{
    ll m;
    ll t;
}ans[200005];
ll cnt = 0, tot = 0, val;
void push_up(int k)
{
    que[k].min = min(que[k << 1].min, que[k << 1 | 1].min);
}
void build(int left, int right, int k)
{
    que[k].l = left;
    que[k].r = right;
    que[k].min = 0;
    if (left == right)
    {
        scanf("%lld", &que[k].min);
        return;
    }
    int mid = (left + right) >> 1;
    build(left, mid, k << 1);
    build(mid + 1, right, k << 1 | 1);
    push_up(k);
}
void query(int left, int right, int k)
{
    if (left == right)
    {
        val = que[k].min;
        que[k].min = LLONG_MAX;
        return;
    }
    int mid = (left + right) >> 1;
    if (tot >= que[k << 1].min)//如果当前区间的左儿子最小值小于等于手中灯泡数，找左边
        query(left, mid, k << 1);
    else//反之，找右边
        query(mid + 1, right, k << 1 | 1);
    push_up(k);
}
int main()
{
    int n, m, t, maxn = 0;
    int q[100005];
    scanf("%d%d", &n, &m);
    build(1, n, 1);
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        scanf("%d", &q[i]);
        maxn = max(maxn, q[i]);
    }
    for (int i = 1; i <= maxn; i++)
    {
        if (cnt != n)//当所有房间灯泡没有被全部更新
        tot += m;
        while (true)
        {
            if (que[1].min > tot)
                break;
            query(1, n, 1);
            tot -= val;
            cnt++;
        }
        ans[i].m = cnt;//记录每一个月份对应的答案
        ans[i].t = tot;
    }
    for (int i = 0; i < t; i++)
        printf("%lld %lld\n", ans[q[i]].m, ans[q[i]].t);
}