題目大意

n個(gè)房間各有一些需要更換的臺(tái)燈。每個(gè)月買m盞，包括上月累積，從左到右對(duì)各房間換燈泡，如果房間里需要更換的數(shù)量大于手中的燈泡數(shù)則跳過(guò)。詢問(wèn)某月累計(jì)對(duì)多少房間更換燈泡，以及剩下的燈泡數(shù)。

思路

線段樹維護(hù)區(qū)間最小值，每次查詢左邊第一個(gè)小于手中燈泡數(shù)的房間。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define INF 0x3f3f3f3f #define rep0(i, n) for (int i = 0; i < n; i++) #define rep1(i, n) for (int i = 1; i <= n; i++) #define rep_0(i, n) for (int i = n - 1; i >= 0; i--) #define rep_1(i, n) for (int i = n; i > 0; i--) #define MAX(x, y) (((x) > (y)) ? (x) : (y)) #define MIN(x, y) (((x) < (y)) ? (x) : (y)) #define mem(x, y) memset(x, y, sizeof(x)) #define MAXN 100010 using namespace std; struct Node {int mn;} tree[MAXN << 2]; int ans[MAXN], rm[MAXN], qu[MAXN]; int a[MAXN]; void push_up(int rt, int l, int r) {if (l == r)return;tree[rt].mn = MIN(tree[rt << 1].mn, tree[rt << 1 | 1].mn); } void build(int rt, int l, int r) {if (l == r){tree[rt].mn = a[l];return;}int mid = (l + r) >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);push_up(rt, l, r);} int update(int rt, int l, int r, int val) {if (tree[rt].mn > val)return 0;if (l == r){int tmp = tree[rt].mn;tree[rt].mn = INF;return tmp;}int mid = (l + r) >> 1;int ans = 0;if (tree[rt << 1].mn <= val)ans = update(rt << 1, l, mid, val);else if (tree[rt << 1 | 1].mn <= val)ans = update(rt << 1 | 1, mid + 1, r, val);push_up(rt, l, r);return ans;}int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif // ONLINE_JUDGEint n, m, q, mx_mon = 0;scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", a + i);build(1, 1, n);scanf("%d", &q);for (int i = 1; i <= q; i++){scanf("%d", qu + i);mx_mon = MAX(mx_mon, qu[i]);}int cnt = n, lmp = 0, mon = 1;for (; mon <= mx_mon; mon++){if (!cnt){ans[mon] = n - cnt;rm[mon] = lmp;continue;}int tmp;lmp += m;while (cnt && (tmp = update(1, 1, n, lmp))){cnt--;lmp -= tmp;}ans[mon] = n - cnt;rm[mon] = lmp;}for (int i = 1; i <= q; i++)printf("%d %d\n", ans[qu[i]], rm[qu[i]]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的计蒜客_Lpl and Energy-saving Lamps_线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。