題目鏈接：hdu 2871 Memory Control

題目大意：模擬一個(gè)內(nèi)存分配機(jī)制。

• Reset：重置，釋放全部空間
• New x：申請內(nèi)存為x的空間，輸出左地址
• Free x：釋放地址x所在的內(nèi)存塊
• Get x：查詢第x個(gè)內(nèi)存塊，輸出左地址

解題思路：一開始全用線段樹去做，寫的亂七八糟，事實(shí)上僅僅要用線段樹維護(hù)可用內(nèi)存。然后用戶一個(gè)vector記錄全部的內(nèi)存塊。

#include <cstdio> #include <cstring> #include <vector> #include <algorithm>using namespace std; const int maxn = 50005;#define lson(x) ((x)<<1) #define rson(x) (((x)<<1)|1) int lc[maxn << 2], rc[maxn << 2], set[maxn << 2]; int L[maxn << 2], R[maxn << 2], S[maxn << 2];inline int length (int u) {return rc[u] - lc[u] + 1; }inline void maintain (int u, int v) {set[u] = v;L[u] = R[u] = S[u] = (v ? 0 : length(u)); }inline void pushup (int u) {S[u] = max( max(S[lson(u)], S[rson(u)]), L[rson(u)] + R[lson(u)]);L[u] = L[lson(u)] + (L[lson(u)] == length(lson(u)) ? L[rson(u)] : 0);R[u] = R[rson(u)] + (R[rson(u)] == length(rson(u)) ? R[lson(u)] : 0); }inline void pushdown (int u) {if (set[u] != -1) {maintain(lson(u), set[u]);maintain(rson(u), set[u]);set[u] = -1;} }void build (int u, int l, int r) {lc[u] = l;rc[u] = r;set[u] = -1;if (l == r) {maintain(u, 0);return;}int mid = (l + r) / 2;build(lson(u), l, mid);build(rson(u), mid + 1, r);pushup(u); }void modify (int u, int l, int r, int v) {if (l <= lc[u] && rc[u] <= r) {maintain(u, v);return;}pushdown(u);int mid = (lc[u] + rc[u]) / 2;if (l <= mid)modify(lson(u), l, r, v);if (r > mid)modify(rson(u), l, r, v);pushup(u); }int query (int u, int len) {if (S[u] < len)return 0;if (lc[u] == rc[u])return lc[u];pushdown(u);int mid = (lc[u] + rc[u]) / 2, ret;if (S[lson(u)] >= len)ret = query(lson(u), len);else if (L[rson(u)] + R[lson(u)] >= len)ret = mid - R[lson(u)] + 1;elseret = query(rson(u), len);pushup(u);return ret; }typedef pair<int, int> pii; int N, M; vector<pii> list;int find (int k) {int l = 0, r = list.size() - 1;while (l <= r) {int mid = (l + r) / 2;if (list[mid].first > k)r = mid - 1;elsel = mid + 1;}return l; }int main () {while (scanf("%d%d", &N, &M) == 2) {build (1, 1, N);list.clear();int k;char op[5];while (M--) {scanf("%s", op);if (op[0] == 'R') {modify(1, 1, N, 0);list.clear();printf("Reset Now\n");} else {scanf("%d", &k);if (op[0] == 'N') {int x = query(1, k);if (x) {modify(1, x, x + k - 1, 1);pii u = make_pair(x, x + k - 1);list.insert(list.begin() + find(x), u);printf("New at %d\n", x);} elseprintf("Reject New\n");} else if (op[0] == 'F') {int x = find(k) - 1;if (x != -1 && k <= list[x].second) {modify(1, list[x].first, list[x].second, 0);printf("Free from %d to %d\n", list[x].first, list[x].second);list.erase(list.begin() + x);} elseprintf("Reject Free\n");} else if (op[0] == 'G') {if (k <= list.size()) {printf("Get at %d\n", list[k-1].first);} elseprintf("Reject Get\n");}}}printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 2871 Memory Control(线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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