【luogu CF1630B】Range and Partition(结论)
Range and Partition
题目链接:
题目大意
给你一个长度为 n 的数组 a,值域是 1~n,和一个数 k,你要选一个值域范围 [x,y],使得数组可以划分成 k 段,每一段 [x,y] 范围内的数比范围外的数都多。 要你求一组 [x,y] 使得 y-x 最小且给出划分方案。
思路
考虑如果给你范围,怎么看最多能划分成多少段。 (段之间可以合并这个很显然)
那我们考虑从左往右看,如果当前段能满足条件就直接结成一个段。 思考这样是否可行,那我们可以首先算出在值域范围比不在至于范围多的数量。 那这个相当于我们的资本,那我们每次肯定是少用点,那剩下的随便啊,就留给最后一个呗。 也不难看到这个多的数量就是能形成的段的最大数量。
然后因为我们的范围是值域的范围,那如果我们固定左端点,右端点越大,这个差肯定越大,考虑找到第一个满足条件的右端点。 而且左端点往右,右端点肯定不会往左,所以右端点是单调的,那一个指针维护即可。 至于求划分方案,就用我们上面的想法,最后一段直接包揽剩下全部即可。
代码
#include<cstdio> using namespace std; namespace IO { char buf[1 << 27], *p1 = buf, *p2 = buf; //inline char nc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; } inline char nc() { return getchar();} inline int readInt() { char ch = nc(); int sum = 0; while (ch < 48 || ch > 57) ch = nc(); while (ch >= 48 && ch <= 57) sum = sum * 10 + ch - 48, ch = nc(); return sum; } } // namespace IO const int N = 2e5 + 100; //const int N = 2e7 + 100; int n, k, num[N]; int ansx, ansy, tmp[N]; void slove() { n = IO::readInt(); k = IO::readInt(); for (int i = 1; i <= n; i++) num[tmp[i] = IO::readInt()]++; for (int i = 1; i <= n; i++) num[i] += num[i - 1]; ansx = 1e9; ansy = 2e9; for (int i = 1, j = 1; i <= n; i++) { while (j <= n && num[j] - num[i - 1] < n - (num[j] - num[i - 1]) + k) j++; if (j > n) break; if (j - i < ansy - ansx || ((j - i == ansy - ansx) && i < ansx)) ansx = i, ansy = j; } printf("%d %d ", ansx, ansy); int sum = 0, lst = 1, numb = 0; for (int i = 1; i <= n; i++) { if (ansx <= tmp[i] && tmp[i] <= ansy) sum++; else sum--; if (sum == 1 && numb != k - 1) { numb++; printf("%d %d ", lst, i); lst = i + 1; sum = 0; } } printf("%d %d ", lst, n); for (int i = 1; i <= n; i++) num[i] = 0; } int main() { int t = IO::readInt(); while (t--) slove(); return 0; }