题目：https://www.luogu.org/problemnew/show/P2751
我的贪心还是太菜了啊...
第一问可以这么想：对于物品i，我们需要选择一个机器j，使得目前j的结束时间+j处理i的时间最小，这样i被处理完的时间也就最短
为什么正确？可以反证，也显然成立
第二问有点儿棘手，但是逆向思维一下，倒着处理：从最后一个被A处理完的物品开始，选择一个j的结束时间 + j处理i的时间最小的j
其实这里可以这么考虑：我们要每个物品的等待时间与处理时间之和尽量小
以上
时间：2.0h
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<queue> #include<vector> using namespace std; const int maxn = 1005; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) { if(ch == ‘-‘) op = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘) { (ans *= 10) += ch - ‘0‘; ch = getchar(); } return ans * op; } struct node { int t,s; bool operator < (const node &k) const { return t > k.t; } }a[maxn]; priority_queue<node> p; int n,m1,m2; int t[maxn]; int main() { n = read(),m1 = read(),m2 = read(); for(int i = 1;i <= m1;i++) { a[i].t = a[i].s = read(); p.push(a[i]);} for(int i = 1;i <= n;i++) { node x = p.top(); p.pop(); t[i] = x.t; x.t += x.s; p.push(x); } printf("%d ",t[n]); while(p.size()) p.pop(); for(int i = 1;i <= m2;i++) { a[i].t = a[i].s = read(); p.push(a[i]);} int ans = 0; for(int i = n;i >= 1;i--) { node x = p.top(); p.pop(); ans = max(ans,t[i] + x.t); x.t += x.s; p.push(x); } printf("%d",ans); }
原文：https://www.cnblogs.com/LM-LBG/p/10087599.html