国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

51Nod - 1099 貪心

2019-11-11 02:03:40
字體:
來源:轉載
供稿:網友

題意:

有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;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 攀枝花市| 旺苍县| 宝鸡市| 周至县| 阿鲁科尔沁旗| 宁波市| 雷山县| 沙坪坝区| 海门市| 福建省| 乳山市| 阿拉善右旗| 长海县| 铜川市| 大洼县| 泸西县| 宁河县| 庆云县| 湛江市| 大连市| 安庆市| 周宁县| 新沂市| 响水县| 县级市| 翼城县| 潼南县| 寿宁县| 绵竹市| 白城市| 栾城县| 开封县| 海晏县| 凤台县| 祁连县| 伊通| 偏关县| 阳城县| 拜泉县| 科技| 高邑县|