【第29题】日拱一卒无有尽功不唐捐终入海[NOIP2012 提高组] 借教室

小码匠

发布于 2023-08-31 14:27:14

1470

发布于 2023-08-31 14:27:14

文章被收录于专栏：小码匠和老码农

[NOIP2012 提高组] 借教室

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P1083
- 参考题解：https://www.luogu.com.cn/problem/solution/P1083
标签：二分、前缀和、差分

思路

如果在一段区间内，连可租用教室数量最少的一天都可以满足订单要求，那么这个订单必定可以满足，然后这段区间的可租用教室数量都需要减去租用的教室数量，如果哪天不可以，后面的每个订单输入即可，不用判断，如果所有订单都可以满足，输出0

代码（考场代码）：45分

#include <bits/stdc++.h>

using namespace std;

void coder() {
	int n, m;
    cin >> n >> m;
    vector <int> v(n);
    for (int i = 0; i < n; ++i) {
    	cin >> v[i];
	}
	bool b = true;
	int t;
	for (int i = 0; i < m; ++i) {
		int d, l, r;
		cin >> d >> l >> r;
		for (int j = l - 1; j < r && b; ++j) {
			if (v[j] < d) {
				b = false;
				t = i + 1;
			}
			v[j] -= d;
		}
	}
	if (!b) {
		cout << -1 << endl;
		cout << t;
	} else {
		cout << 0;
	}
}
int main() {
    coder();
    return 0;
}

代码：90

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

typedef long long LL;
struct edge {
    int l, r;
    LL m, add;
};

struct Segment_Tree {
    vector<edge> t;
    vector<LL> a;

    Segment_Tree(int n) : t(4 * n), a(n + 1) {}

    void push_up(int u) {
        t[u].m = min(t[u << 1].m, t[u << 1 | 1].m);
    }

    void push_down(int u) {
        auto &root = t[u], &left = t[u << 1], &right = t[u << 1 | 1];
        if (root.add) {
            left.add += root.add;
            left.m += root.add;
            right.add += root.add;
            right.m += root.add;
            root.add = 0;
        }
    }

    void build(int u, int l, int r) {
        t[u].l = l;
        t[u].r = r;
        if (l == r) {
            t[u].m = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }

    LL query(int u, int l, int r) {
        if (t[u].l >= l && t[u].r <= r) {
            return t[u].m;
        }
        push_down(u);
        int mid = t[u].l + t[u].r >> 1;
        LL s = 0x7f7f7f7f7f7f;
        if (l <= mid) {
            s = min(s, query(u << 1, l, r));
        }
        if (r > mid) {
            s = min(s, query(u << 1 | 1, l, r));
        }
        return s;
    }

    void cnt(int u, int l, int r, LL v) {
        if (t[u].l >= l && t[u].r <= r) {
            t[u].m += v;
            t[u].add += v;
        } else {
            push_down(u);
            int mid = t[u].l + t[u].r >> 1;
            if (l <= mid) {
                cnt(u << 1, l, r, v);
            }
            if (r > mid) {
                cnt(u << 1 | 1, l, r, v);
            }
            push_up(u);
        }
    }
};

void best_coder() {
    int n, m;
    cin >> n >> m;
    Segment_Tree st(n);
    for (int i = 1; i <= n; ++i) {
        cin >> st.a[i];
    }

    st.build(1, 1, n);
    bool b = false;
    int t = 0;
    for (int i = 0; i < m; ++i) {
        int d, l, r;
        cin >> d >> l >> r;
        if (b) {
            continue;
        }
        if (st.query(1, l, r) >= d) {
            st.cnt(1, l, r, -d);
        } else {
            b = true;
            t = i + 1;
        }
    }
    if (b) {
        cout << -1 << endl;
        cout << t;
    } else {
        cout << 0;
    }
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

代码：AC

在上一版基础上，做了如下优化，依然95分
- 快读
- 手写min函数
- 循环变量：register
洛谷提交时：开启 O2 优化，AC

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

typedef long long LL;

inline void read(int &x) {
    char c = getchar();
    int p = 1;
    x = 0;
    while (!isdigit(c)) {
        if (c == '-') {
            p = -1;
        }
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ '0');
        c = getchar();
    }
    x *= p;
}

inline int _min(int a, int b) {
    return a > b ? b : a;
}

struct edge {
    int l, r, m, add;
};

struct Segment_Tree {
    vector<edge> t;
    vector<int> a;

    Segment_Tree(int n) : t(4 * n), a(n + 1) {}

    void push_up(int u) {
        t[u].m = _min(t[u << 1].m, t[u << 1 | 1].m);
    }

    void push_down(int u) {
        auto &root = t[u], &left = t[u << 1], &right = t[u << 1 | 1];
        if (root.add) {
            left.add += root.add;
            left.m += root.add;
            right.add += root.add;
            right.m += root.add;
            root.add = 0;
        }
    }

    void build(int u, int l, int r) {
        t[u].l = l;
        t[u].r = r;
        if (l == r) {
            t[u].m = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }

    int query(int u, int l, int r) {
        if (t[u].l >= l && t[u].r <= r) {
            return t[u].m;
        }
        push_down(u);
        int mid = t[u].l + t[u].r >> 1;
        int s = 0x7f7f7f7f;
        if (l <= mid) {
            s = _min(s, query(u << 1, l, r));
        }
        if (r > mid) {
            s = _min(s, query(u << 1 | 1, l, r));
        }
        return s;
    }

    void cnt(int u, int l, int r, int v) {
        if (t[u].l >= l && t[u].r <= r) {
            t[u].m += v;
            t[u].add += v;
        } else {
            push_down(u);
            int mid = t[u].l + t[u].r >> 1;
            if (l <= mid) {
                cnt(u << 1, l, r, v);
            }
            if (r > mid) {
                cnt(u << 1 | 1, l, r, v);
            }
            push_up(u);
        }
    }
};

void best_coder() {
    int n, m;
    read(n);
    read(m);
    Segment_Tree st(n);
    for (register int i = 1; i <= n; ++i) {
        read(st.a[i]);
    }

    st.build(1, 1, n);
    bool b = false;
    int t = 0;
    for (register int i = 0; i < m; ++i) {
        int d, l, r;
        read(d);
        read(l);
        read(r);
        if (b) {
            continue;
        }
        if (st.query(1, l, r) >= d) {
            st.cnt(1, l, r, -d);
        } else {
            b = true;
            t = i + 1;
        }
    }
    if (b) {
        printf("%d\n", -1);
        printf("%d", t);
    } else {
        printf("%d", 0);
    }
}

int main() {
    // 提升cin、cout效率
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-05-31，如有侵权请联系 cloudcommunity@tencent.com 删除

add