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

首頁(yè) > 學(xué)院 > 開發(fā)設(shè)計(jì) > 正文

51Nod - 1099 貪心

2019-11-11 02:02:43
字體:
供稿:網(wǎng)友

題意:

有N個(gè)任務(wù)需要執(zhí)行,第i個(gè)任務(wù)計(jì)算時(shí)占R[i]個(gè)空間,而后會(huì)釋放一部分,最后儲(chǔ)存計(jì)算結(jié)果需要占據(jù)O[i]個(gè)空間(O[i] < R[i])。例如:執(zhí)行需要5個(gè)空間,最后儲(chǔ)存需要2個(gè)空間。給出N個(gè)任務(wù)執(zhí)行和存儲(chǔ)所需的空間,問執(zhí)行所有任務(wù)最少需要多少空間。Input
第1行:1個(gè)數(shù)N,表示任務(wù)的數(shù)量。(2 <= N <= 100000)第2 - N + 1行:每行2個(gè)數(shù)R[i]和O[i],分別為執(zhí)行所需的空間和存儲(chǔ)所需的空間。(1 <= O[i] < R[i] <= 10000)Output
輸出執(zhí)行所有任務(wù)所需要的最少空間。Input示例
2014 12 111 320 47 56 520 719 89 420 1018 1112 613 1214 915 216 1517 1519 1320 220 1Output示例
135

思路:

簡(jiǎn)單貪心,比較兩個(gè)任務(wù)不同執(zhí)行順序結(jié)果的大小來定義任務(wù)先后,然后按優(yōu)先級(jí)排序即可。

代碼:

#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;}
發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 来凤县| 封丘县| 万安县| 合川市| 鱼台县| 台州市| 云浮市| 稻城县| 洪雅县| 四川省| 陆良县| 伽师县| 荥阳市| 平度市| 平顶山市| 镇宁| 广元市| 盐山县| 兰考县| 韶山市| 汉中市| 准格尔旗| 农安县| 教育| 顺平县| 双城市| 岱山县| 灵台县| 长垣县| 辽源市| 微博| 阳春市| 长沙县| 荃湾区| 梅州市| 嘉义县| 奉节县| 雷州市| 渑池县| 雷州市| 多伦县|