第一，你居然敢看题解，必须批评
第二，看到ml13出现疑似备课的行为，那必须给学弟学妹整个活
首先啊，这道题目既然要整活，那肯定不能按照标签上的“队列”“尺取法”来做
然后，第二眼，这道题目扫一眼之后发现有效时间间隔最大只有45
OK，整活开始
解法①
使用无序map（ unordered_map ）
因为 ，这个范围直接开数组肯定会直接爆炸，那么会想到用map存，但是 map 复杂度访问一次是 的，时间范围又容易炸
所以这时候就要用unordered_map,他的复杂度有一定常数，但总体比map快，不过他就不能用迭代器遍历了，仅仅只能存数据
所以我们可以直接暴力遍历法，具体代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+10,P = 1e9;
int n,ans;
int tot = 1;
unordered_map <int,int> a;
struct node{
int l,r,maxx;
}tree[maxn*35];
int read(){ //快读，加快你的读入
int res = 0;
char ch;
ch = getchar();
while(ch < '0' || ch > '9'){
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
res = res*10 + ch - '0';
ch = getchar();
}
return res;
}
signed main()
{
cin>>n;
while(n--){
int op;
op = read();
if(op == 0){
int x,t;
x=read();
t=read();
a[t] = x;
ans+=x;
}
else{
int x,t;
x=read();
t=read();
int id = 0;
for(int i=t-45;i<=t;i++){ //直接从前45s暴力遍历
if(a[i] >= x){
id = i;
break;
}
}
if(id != 0)a[id] = 0;
else ans += x;
}
}
cout<<ans<<endl;
return 0;
}
你会发现这段代码思维量非常的少，但是他有一点慢，总时间1000多ms
没关系，我们还有
解法②
线段树维护
做法类似，直接暴力遍历，用线段树维护区间最大值
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+10,P = 1e9;
int n,ans;
int tot = 1;
struct node{
int l,r,maxx;
}tree[maxn*35];
int read(){
int res = 0;
char ch;
ch = getchar();
while(ch < '0' || ch > '9'){
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
res = res*10 + ch - '0';
ch = getchar();
}
return res;
}
int update(int p,int l,int r,int x,int u){
if(p == 0){
p = ++tot;
}
if(l == r){
tree[p].maxx = u;
return p;
}
int mid = l+r >> 1;
int lx = tree[p].l;
int rx = tree[p].r;
if(x <= mid) tree[p].l = update(lx,l,mid,x,u);
else tree[p].r = update(rx,mid+1,r,x,u);
lx = tree[p].l;
rx = tree[p].r;
//cout<<l<<" "<<r<<" "<<endl;
tree[p].maxx = max(tree[lx].maxx , tree[rx].maxx);
return p;
}
void repair(int p,int l,int r,int x){
if(p == 0)return ;
if(l == r){
tree[p].maxx = 0;
return ;
}
int mid = l+r >> 1;
int lx = tree[p].l;
int rx = tree[p].r;
if(x <= mid) repair(lx,l,mid,x);
else repair(rx,mid+1,r,x);
lx = tree[p].l;
rx = tree[p].r;
tree[p].maxx = max(tree[lx].maxx , tree[rx].maxx);
return ;
}
int solve(int p,int l,int r,int b,int e){
if(p == 0)return INT_MIN;
if(l > e || r < b)return INT_MIN;
if(b <= l && r <= e)return tree[p].maxx;
int mid = l+r>>1;
int lx = tree[p].l;
int rx = tree[p].r;
return max(solve(lx,l,mid,b,e),solve(rx,mid+1,r,b,e));
}
signed main()
{
cin>>n;
while(n--){
int op;
op = read();
if(op == 0){
int x,t;
x=read();
t=read();
update(1,1,P,t,x);
ans+=x;
}
else{
int x,t;
x=read();
t=read();
if(solve(1,1,P,t-45,t) < x){
ans += x;
}
else{
int id = 0;
for(int i=t-45;i<=t;i++){
int tmp = solve(1,1,P,i,i);
if(x <= tmp){
id = i;
break;
}
}
repair(1,1,P,id);
}
}
}
cout<<ans<<endl;
return 0;
}
你会发现，这段代码虽然思维复杂度变高了，但是时间也变成了2000多ms，明显这个算法对于整活来说更加的成功
解法③
所以理论上， 这个复杂度如果你会快读，应该也卡的过去
所以你直接用map应该问题也不大
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10, P = 1e9;
int n, ans;
int tot = 1;
map<int, int> a;
struct node {
int l, r, maxx;
} tree[maxn * 35];
int read() {
int res = 0;
char ch;
ch = getchar();
while (ch < '0' || ch > '9') {
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
res = res * 10 + ch - '0';
ch = getchar();
}
return res;
}
signed main() {
cin >> n;
while (n--) {
int op;
op = read();
if (op == 0) {
int x, t;
x = read();
t = read();
a[t] = x;
ans += x;
} else {
int x, t;
x = read();
t = read();
int id = 0;
for (int i = t - 45; i <= t; i++) {
if (a[i] >= x) {
id = i;
break;
}
}
if (id != 0)
a[id] = 0;
else
ans += x;
}
}
cout << ans << endl;
return 0;
}
更更更NB的是，他的时间直接卡到3000ms +，这不直接炸裂
共 2 条回复
手动点赞完毕
整活不易，点个赞呗