题意简述

题目传送门

现在又一些软件,第 ii 个软件运行的时候会占用 aiGBa_i GB 的内存(程序停止运行后会停止占用内存),运行结束后会使你的电脑额外增加 biGBb_iGB 的内存,你的电脑原来有 kGBkGB 内存,请问在运行完这些软件后内存最多为多少(每个软件只能运行一次)

思路

非常水的一道题

很显然使用结构体将 aia_ibib_i 捆绑起来,并以 aia_i 为关键词排序,能运行时就直接运行软件,如果运行不了就结束。

正确性显然。

代码

#include <bits/stdc++.h>
using namespace std;

template<class T>
inline char read(T &ret) {
	ret = 0;
	char c = getchar();
	short f = 1;
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c <= '9' && c >= '0') {
		ret = (ret << 3) + (ret << 1) + c - 48;
		c = getchar();
	}
	ret *= f;
	return c;
}

int T;
int N , K;
int A[110] , B[110];
multiset<pair<int , int> > SoftWare;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while(T--) {
		memset(A , 0 , sizeof A);
		memset(B , 0 , sizeof B);
		SoftWare.clear();
		cin >> N >> K;
		for(int i = 1; i <= N; i++) {
			cin >> A[i];
		}
		for(int j = 1; j <= N; j++) {
			cin >> B[j];
		}
		for(int i = 1; i <= N; i++) {
			SoftWare.insert(make_pair(A[i] , B[i]));
		}
		for(multiset<pair<int , int> >::iterator it = SoftWare.begin(); it != SoftWare.end(); it++) {
			if(it -> first <= K) {
				K += it -> second;
			}
			else break;
		}
		cout << K << endl;
	}
	return 0;
}