听灌多(江湖救急)
  • 板块灌水区
  • 楼主FChang
  • 当前回复12
  • 已保存回复12
  • 发布时间2024/9/6 19:01
  • 上次更新2024/9/6 21:33:34
查看原帖
听灌多(江湖救急)
744853
FChang楼主2024/9/6 19:01
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;

int n;

struct node {
	int a,b,sum;
	bool operator <(const node bb) const {
		return b < bb.b;
	}
} a[N];

struct kkk {
	int num, ad;
};

struct xds_tree {
	kkk tree[N << 2];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
	void pushup(int x) {
		if(tree[ls].ad <= tree[rs].ad) return void(tree[x] = tree[ls]);
		return void(tree[x] = tree[rs]);
	}
	void build(int x,int l,int r) {
		if(l==r) return void(tree[x].ad = a[l].sum),void(tree[x].num = l);
		build(ls,l,mid), build(rs,mid+1,r);
		return void(pushup(x));
	}
	void update(int x,int l,int r,int L,int d) {
		if(l==r && r==L) return void(tree[x].ad = d);
		if(L<=mid) update(ls,l,mid,L,d);
		else update(rs,mid+1,r,L,d);
		return void(pushup(x));
	}
	kkk query(int x,int l,int r,int L,int R) {
		if(l>=L&&r<=R) return tree[x];
		kkk res = {0,1e12};
		if(L<=mid) res = query(ls,l,mid,L,R);
		if(R>mid) {
			kkk p = query(rs,mid+1,r,L,R);
			if(p.ad < res.ad) res = p;
		}
		return res;
	}
} T;

signed main() {
//	freopen("boast.in","r",stdin);
//	freopen("boast.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>a[i].a>>a[i].b;
		a[i].sum = a[i].a + a[i].b;
	}
	sort(a+1,a+1+n);
	T.build(1,1,n);
	int sum = 0, ans = 1e12;
	for(int i=1; i<n-1; ++i) {
		sum = a[i].a;
		kkk q = T.query(1,1,n,i+1,n);
		sum += q.ad;
		T.update(1,1,n,q.num,INT_MAX);
		sum += T.query(1,1,n,i+1,n).ad;
		T.update(1,1,n,q.num,q.ad);
		ans = min(ans,sum);
	}
	cout<<ans<<"\n";
	return 0;
}




这段代码在-O2 -std=c++14 环境下,会CE,但是dev-c++编译错误但是继续运行(能过大样例),这是为什么。

2024/9/6 19:01
加载中...