【题解】JZOJ6645 / 洛谷P4090 [USACO17DEC] Greedy Gift Takers P

题解】JZOJ6645 / 洛谷P4090 [USACO17DEC] Greedy Gift Takers P"/>

【题解】JZOJ6645 / 洛谷P4090 [USACO17DEC] Greedy Gift Takers P

洛谷 P4090 [USACO17DEC] Greedy Gift Takers P

题意

n n n 头牛排成一列，队头的奶牛 i i i 拿一个礼物并插到从后往前数 c i c_i ci​ 头牛的前面，重复无限次，问多少奶牛没有礼物。

题解

发现若一头牛无法获得礼物，那么它后面的牛都无法获得礼物。

发现获得礼物的牛构成一个循环。

二分获得礼物的牛的数量。假设有 x x x 头牛获得礼物，仅考虑第 x x x 头牛能否获得礼物。让它获得礼物，就要把它推到前面去。假设前 x − 1 x-1 x−1 头牛都能获得礼物。于是把前 x − 1 x-1 x−1 头牛按 a a a 从小到大排序，也就是把牛尽可能往后插。

假设牛 x x x 后面有 l i m lim lim 头牛。若 x x x 前面的牛 i i i 满足 a i > l i m a_i>lim ai​>lim，那么这个 x x x 无法获得礼物。因为 i i i 会插入到 x x x 的前面，又因为 a a a 值从小到大，那么 i i i 后面的牛都会插到 x x x 前面。若 a i ≤ l i m a_i\le lim ai​≤lim， x x x 后面的牛多一头， l i m lim lim 加 1 1 1。

代码

#include <bits/stdc++.h>
using namespace std;
template<typename Ty> void read(Ty &x) {int c = getchar(), f = 1;for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;for (x = 0; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);x *= f;
}
const int N = 100005;
int n, a[N], b[N], ans = 0;
bool check(int x) {for (int i = 1; i < x; i++) b[i] = a[i];sort(b + 1, b + x);int lim = n - x;for (int i = 1; i < x; i++, lim++)if (b[i] > lim)return 0;return 1;
}
int main() {read(n);for (int i = 1; i <= n; i++) read(a[i]);int l = 0, r = n;while (l <= r) {int mid = l + r >> 1;if (check(mid)) l = mid + 1, ans = mid;else r = mid - 1;}printf("%d", n - ans);return 0;
}