solution
显然的,越小的就应该越优先考虑。所以我们先按照从小到大排序。
然后我们用记录下现在已经选择的建筑所需要花费的时间。如果加上当前建筑的不大于当前建筑的。那么就直接将这个建筑修复即可。
那么如果应该怎么办呢?有两种选择,一种是从前面选的里面踢掉一个(只会踢掉一个,因为每个建筑的贡献都是1),换成当前的。另一种是不选当前的这个。第二种选择的话就直接跳过处理下一个就行了。对于第一个选择我们就要考虑应该踢掉哪一个,因为每个建筑的贡献都是1,所以显然我们踢掉花费时间最大的那个更优秀。所以就用一个堆来维护出当前选择的建筑中花费时间最大的那个,如果踢掉最大的那个之后可以加入当前的这个新的并且总花费时间更小。我们就加入他。
时间复杂度
code
/* * @Author: wxyww * @Date: 2020-05-25 14:53:02 * @Last Modified time: 2020-05-25 14:59:14 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 150010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } #define pi pair<int,int> pi a[N]; priority_queue<int>q; int main() { int n = read(); for(int i = 1;i <= n;++i) { a[i].second = read(),a[i].first = read(); } sort(a + 1,a + n + 1); ll now = 0,ans = 0; for(int i = 1;i <= n;++i) { if(now + a[i].second <= a[i].first) { now += a[i].second; ans++; q.push(a[i].second); } else if(!q.empty() && q.top() > a[i].second) { now -= q.top();now += a[i].second; q.pop();q.push(a[i].second); } } cout<<ans<<endl; return 0; }