题解 | Seating-牛客假日团队赛3I题
I-Seating_牛客假日团队赛3
https://ac.nowcoder.com/acm/contest/945/I
题目描述
To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has N seats in a row. Initially, they are all empty.
Throughout the day, there are M different events that happen in sequence at the restaurant . The two types of events that can happen are:
1. A party of size p arrives . Bessie wants to seat the party in a contiguous block of p empty seats. If this is possible, she does so in the lowest position possible in the list of seats. If it is impossible, the party is turned away.
2. A range [a,b] is given , and everybody in that range of seats leaves. Please help Bessie count the total number of parties that are turned away over the course of the day.
输入描述:
* Line 1: Two space-separated integers, and .* Lines 2..M+1: Each line describes a single event. It is either aline of the form "A p" (meaning a party of size p arrives) or"L a b" (meaning that all cows in the range leave).
输出描述:
* Line 1: The number of parties that are turned away.
示例1
输入
10 4
A 6
L 2 4
A 5
A 2
输出
1
说明
INPUT DETAILS:
There are 10 seats, and 4 events. First, a party of 6 cows arrives. Then
all cows in seats 2..4 depart. Next, a party of 5 arrives, followed by a
party of 2.
OUTPUT DETAILS:
Party #3 is turned away. All other parties are seated.
解答
想起大一的时候小学期做过同样的题目,不过那个时候得到数据规模是很小的,所以当时的我是暴力做的。
拿到这个题,第一个想到线段树,去记录区间可用的seat有多少个。这么做还不够,还需要能找到安排时最左的满足条件的坐标。
那线段树就需要再多记录两个元素。一个是从左往右数空闲位置的个数,另一个是从右往左树空闲位置的个数。
说的再多,也不如代码清楚:
来源:Bing_Bodybuilding
拿到这个题,第一个想到线段树,去记录区间可用的seat有多少个。这么做还不够,还需要能找到安排时最左的满足条件的坐标。
那线段树就需要再多记录两个元素。一个是从左往右数空闲位置的个数,另一个是从右往左树空闲位置的个数。
说的再多,也不如代码清楚:
#include<bits/stdc++.h> using namespace std; const int maxn = 500000 + 10; // static const int maxn = 15; const int REMOVE_ALL = 1; const int PLACE = 2; const int mi = maxn*3; class Node { public: int numFromLeft; int numFromRight; int value; int lazyType; Node(int numFromLeft, int numFromRight, int value, int lazyType) { this->numFromLeft = numFromLeft; this->numFromRight = numFromRight; this->value = value; this->lazyType = lazyType; } Node() {} }; Node nodes[maxn * 4]; // static { // for (int i = 0; i < nodes.length; ++i) // nodes[i] = new Node(); // } void updateLeftRight(int l, int r, int curr) { int mid = (l + r) >> 1; nodes[curr].numFromLeft = (nodes[curr << 1].value == (mid - l + 1)) ? nodes[curr << 1].value + nodes[curr << 1 | 1].numFromLeft : nodes[curr << 1].numFromLeft; nodes[curr].numFromRight = (nodes[curr << 1 | 1].value == (r - mid)) ? nodes[curr << 1 | 1].value + nodes[curr << 1].numFromRight : nodes[curr << 1 | 1].numFromRight; } void pushUp(int l, int r, int curr) { updateLeftRight(l, r, curr); // considering merge sort nodes[curr].value = max( max(nodes[curr << 1].value, nodes[curr << 1 | 1].value), nodes[curr << 1].numFromRight + nodes[curr << 1 | 1].numFromLeft ); } void pushDown(int l, int r, int curr) { nodes[curr << 1].lazyType = nodes[curr << 1 | 1].lazyType = nodes[curr].lazyType; int m = (l + r) >> 1; if (nodes[curr].lazyType == REMOVE_ALL) { nodes[curr << 1].numFromLeft = nodes[curr << 1].numFromRight = nodes[curr << 1].value = m - l + 1; nodes[curr << 1 | 1].numFromLeft = nodes[curr << 1 | 1].numFromRight = nodes[curr << 1 | 1].value = r - m; } else if (nodes[curr].lazyType == PLACE) { nodes[curr << 1].numFromLeft = nodes[curr << 1].numFromRight = nodes[curr << 1].value = 0; nodes[curr << 1 | 1].numFromLeft = nodes[curr << 1 | 1].numFromRight = nodes[curr << 1 | 1].value = 0; } nodes[curr].lazyType = 0; } void build(int left, int right, int curr) { if (left == right) { nodes[curr].numFromLeft = nodes[curr].numFromRight = nodes[curr].value = 1; return; } int mid = (left + right) >> 1; build(left, mid, curr << 1); build(mid + 1, right, curr << 1 | 1); pushUp(left, right, curr); } void update(int targetL, int targetR, int operationType, int l, int r, int curr) { if (nodes[curr].lazyType != 0 && curr * 2 + 1 < mi) pushDown(l, r, curr); // the whole interval if (targetL <= l && r <= targetR) { if (operationType == REMOVE_ALL) nodes[curr].numFromLeft = nodes[curr].numFromRight = nodes[curr].value = r - l + 1; if (operationType == PLACE) nodes[curr].numFromLeft = nodes[curr].numFromRight = nodes[curr].value = 0; nodes[curr].lazyType = operationType; return; } int mid = (l + r) >> 1; if (targetL <= mid) update(targetL, targetR, operationType, l, mid, curr << 1); if (targetR > mid) update(targetL, targetR, operationType, mid + 1, r, curr << 1 | 1); pushUp(l, r, curr); } int query(int requiredSeats, int left, int right, int curr) { if (nodes[curr].lazyType != 0) pushDown(left, right, curr); if (left == right) return left; int m = (left + right) >> 1; // There are enough seats in the left part if (nodes[curr << 1].value >= requiredSeats) return query(requiredSeats, left, m, curr << 1); // Cross two sub-intervals else if (nodes[curr << 1].numFromRight + nodes[curr << 1 | 1].numFromLeft >= requiredSeats) return m - nodes[curr << 1].numFromRight + 1; // try to look for it in the right part else return query(requiredSeats, m + 1, right, curr << 1 | 1); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; // long start = System.currentTimeMillis(); // for (int i = 0; i < nodes.length; ++i) // nodes[i] = new Node(); // long end = System.currentTimeMillis(); // System.out.println((end - start)); // System.exit(-1); cin >> n >> m; build(1, n, 1); // int foo =(int) (Math.log(n)/Math.log(2) + 1) * 2; // System.out.println(foo); // System.exit(0); int num = 0; for (int i = 1; i <= m; i++) { char cmd; cin >> cmd; if (cmd == 'A') { int x; cin >> x; if (nodes[1].value >= x) { int ans = query(x, 1, n, 1); update(ans, ans + x - 1, PLACE, 1, n, 1); } else num++; } else { int l, r; cin >> l >> r; update(l, r, REMOVE_ALL, 1, n, 1); } } cout << num << endl; }
来源:Bing_Bodybuilding