听书上说有贪心 + 数据结构的做法,研究了一下。
朴素贪心
考虑把所有线段按照右端点 $b$ 从小到大排序,依次考虑每一条线段的要求:
- 如果已经满足要求则跳过
- 否则尽量选择靠后的数(因为之后的线段的右端点都在这条线段的右边,这样容错更高)
所以,我们可以建一个数组,$d[i]$ 表示 $i$ 数字是否选择(填$1$或$0$),扫一遍 $[l, r]$ 区间求和,然后从后往前贪心放数即可。
对于每条线段需要 $O(r - l + 1)$。所以最坏情况下 $O(n ^ 2)$。但是轻松 $52ms$ 过了。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;
int n, d[N], c[N];
struct Seg{
int a, b, c;
bool operator < (const Seg &x) const {
return b < x.b;
}
}e[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
sort(e + 1, e + 1 + n);
int ans = 0;
for (int i = 1; i <= n; i++) {
int l = e[i].a, r = e[i].b, cnt = e[i].c;
for (int j = l; j <= r; j++)
cnt -= d[j];
if(cnt > 0) {
for (int j = r; j >= l && cnt; j--)
if(!d[j]) cnt--, ans++, d[j] = 1;
}
}
printf("%d\n", ans);
return 0;
}
优化
考虑用数据结构优化。
发现我们需要三个操作:
- 询问 $[l, r]$ 区间的数字个数
- 将值为 $x$ 的位置 $+1$
-
从后往前,找到比当前位置靠前的下一个 $0$ 的位置。
-
前两个就是 “区间求和,单调修改”,典型的树状数组。$O(nlog_250000) $
-
第三种操作,可以用并查集优化。为什么可以确保时间复杂度呢?对于每一条线段,最多只有一次会枚举到 $1$ (即开始的那一次),之后每次枚举都会枚举到 $0$ 的位置,即$d[i] = 0$,然后把它变成 $1$,而以后就不会访问到了。而一共有 $50000$ 个值,所以复杂度是 $O(50000log_n)$
$33ms$
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50001;
int n, d[N], c[N], f[N];
struct Seg{
int a, b, c;
bool operator < (const Seg &x) const {
return b < x.b;
}
}e[N];
// 树状数组
int inline ask(int x) {
int res = 0;
for (; x; x -= x & -x) res += c[x];
return res;
}
void inline add(int x) {
for (; x < N; x += x & -x) c[x]++;
}
// 并茶集:find(x) 表示找到 <= x 中最大的一个是 0 的数
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < N; i++) f[i] = i;
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
sort(e + 1, e + 1 + n);
int ans = 0;
for (int i = 1; i <= n; i++) {
int l = e[i].a, r = e[i].b, cnt = e[i].c;
// 取 [l, r] 选了多少个数
cnt -= ask(r) - ask(l - 1);
if(cnt > 0) {
for (int j = r; j >= l && cnt; ) {
// d[j] == 1 的情况每条线段至多出现一次
if(!d[j]) {
cnt--, ans++, d[j] = 1;
// j 被标记成 1 了,要指向 find(j - 1)
f[j] = j - 1;
// 维护树状数组
add(j);
};
if(find(j) != j) j = f[j];
else j--;
}
}
}
printf("%d\n", ans);
return 0;
}
大佬,现在朴素贪心好像过不了,在最后一个点会T
不需要使用并查集,直接用一个stack就可以了,时间复杂度O(nlogn),AC 118 ms
你好,时间复杂度为什么是$Olog(n)$
同样思路,
然后从后往前贪心放数即可。
对于这个可以用链表链接0(没选的元素) 可以保证O(N)
现在还能提交通过吗
过不了,需要把ask的 结束判断 改一下
读入的时候,a,b,就行了
其实就是因为树状数组不能从下标从0开始所以把输入的地方a,b就可以了
请问这个优化从后往前,找到比当前位置靠前的下一个 00 的位置。 有必要嘛
我加了和没加时间是一样的 请问是为什么呢
有必要的。最近我做cf一个题不这样就T了。。
只是这道题数据没有故意卡这个位置 否则就会O(N^2)容易超时
如果这题用差分约束是不是只能求最少有多少个1,不能求哪些位置有1
orz
但是有个地方没有看懂
那个树状数组求和为什么 x < N 而不是 x <= n?
还有并查集初始化的时候那个也是为什么用 N
望高人指点
因为N是数组长度…
但是如果 n 没有那么大后面的东西不会用不到吗
用不到会错吗
orz
Orz
orz
不过 注释里有个 ” 并茶集 ” 233
昏睡红茶(喜)
Orz,
第二个
if(find(j) != j) j = f[j];
else j–;
这里是没必要的 j = f[j] 就行, 不管 j 这个位置有没有, 经过放数操作, j这个位置必定有数
太强了
ORZ大佬niubility
差点忘了ability