题目

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
long long g[200001][2]={0},t,n,to=0;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int getStandard(int i, int j) {
    int key = g[i][1];
    while (i < j) {
        while (i < j && g[j][1] >= key) {
            j--;
        }
        if (i < j) {
            g[i][1] = g[j][1];
            g[i][2] = g[j][2];
        }
        while (i < j && g[i][1] <= key) {
            i++;
        }
        if (i < j) {
            g[j][1] = g[i][1];
            g[j][2] = g[i][2];
        }
    }
    g[i][1] = key;
    return i;
}
void QuickSort(int low, int high) {
    if (low < high) {
        int standard = getStandard( low, high);
        QuickSort(low, standard - 1);
        QuickSort(standard + 1, high);
    }
}
int main(){
	n=read();
	t=read();
	to=0;
	for(int i=1;i<=n;i++){
		g[i][1]=read();
		g[i][2]=read();
		to+=g[i][2];
	}
	to+=t;
	QuickSort(1,n);
	for(int i=n;i>=1;i--){
		if(g[i][1]>to-g[i][2])
			to-=g[i][2];
		else break;
	}
	printf("%d",to);
}

为什么02+快排+快读解决超时还错了...awsl

然而如果只有快排反而TLE了

#include<bits/stdc++.h>
using namespace std;
long long g[200001][2]={0},t,n,to=0;
int getStandard(int i, int j) {
    int key = g[i][1];
    while (i < j) {
        while (i < j && g[j][1] >= key) {
            j--;
        }
        if (i < j) {
            g[i][1] = g[j][1];
            g[i][2] = g[j][2];
        }
        while (i < j && g[i][1] <= key) {
            i++;
        }
        if (i < j) {
            g[j][1] = g[i][1];
            g[j][2] = g[i][2];
        }
    }
    g[i][1] = key;
    return i;
}
 
void QuickSort(int low, int high) {
    if (low < high) {
        int standard = getStandard( low, high);
        QuickSort(low, standard - 1);
        QuickSort(standard + 1, high);
    }
}
int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>g[i][1]>>g[i][2];
		to+=g[i][2];
	}
	to+=t;
	QuickSort(1,n);
	for(int i=n;i>=1;i--){
		if(g[i][1]>to-g[i][2])
			to-=g[i][2];
		else break;
	}
	cout<<to;
}

记录： https://atcoder.jp/contests/abc203/submissions/24000552

https://atcoder.jp/contests/abc203/submissions/23069593