大意略。
思路:要时间最短,即要求尽量多的任务并发进行,则把执行时间由大到小排序即可。
#include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <stack> #include <algorithm> #include <cctype> using namespace std; const int maxn = 1010; struct node { int B, J; bool operator < (const node &a) const { return J > a.J; } }A[maxn]; int n; int read_case() { scanf("%d", &n); if(!n) return 0; for(int i = 0; i < n; i++) scanf("%d%d", &A[i].B, &A[i].J); return 1; } void solve() { sort(A, A+n); int ans = A[0].B + A[0].J, t = 0; for(int i = 0; i < n; i++) { t += A[i].B; ans = max(ans, t+A[i].J); } printf("%d\n", ans); } int main() { int times = 0; while(read_case()) { printf("Case %d: ", ++times); solve(); } return 0; }