51Nod - 1099 贪心

2019-11-11 02:02:43

字体：大中小

来源：转载

供稿：网友

题意：

有N个任务需要执行，第i个任务计算时占R[i]个空间，而后会释放一部分，最后储存计算结果需要占据O[i]个空间（O[i] < R[i]）。例如：执行需要5个空间，最后储存需要2个空间。给出N个任务执行和存储所需的空间，问执行所有任务最少需要多少空间。Input

第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;}