第1行:1個數N,表示任務的數量。(2 <= N <= 100000)第2 - N + 1行:每行2個數R[i]和O[i],分別為執行所需的空間和存儲所需的空間。(1 <= O[i] < R[i] <= 10000)Output輸出執行所有任務所需要的最少空間。Input示例2014 12 111 320 47 56 520 719 89 420 1018 1112 613 1214 915 216 1517 1519 1320 220 1Output示例135思路:
簡單貪心,比較兩個任務不同執行順序結果的大小來定義任務先后,然后按優先級排序即可。代碼:
#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 10;struct node { int x, y; bool Operator < (const node &rhs) const { return y + rhs.x < x + rhs.y; }}a[MAXN];int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i].x, &a[i].y); } sort (a + 1, a + 1 + n); int now = 0, ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, now + a[i].x); now += a[i].y; } PRintf("%d/n", ans); return 0;}
新聞熱點
疑難解答