UVA11269 题解

一、题目翻译

题目描述

$ Sultan $ 和 $ GolaphiBaba $ 两个人想一起出一个比赛。$ Sultan $ 负责出题而 $ GolaphiBaba $ 负责数据。请你求出他们出完这场比赛所需要的最短时间。

输入格式

输入会有多组数据，每组数据包含 $3$ 行：

• 第一行包含一个正整数 $N$，代表这场比赛有 $N$ 道题
• 第二行包含 $N$ 个正整数 $S_i$，表示 $ Sultan $ 出第 $i$ 道题所需的时间
• 第三行包含 $N$ 个正整数 $G_i$，表示 $ GolaphiBaba $ 为第 $i$ 道题配数据所需的时间

输出格式

对于每组数据，输出一行，表示 $ Sultan $ 和 $ GolaphiBaba $ 出完这场比赛所需要的最短时间。

二、题目分析

对于一个最优解问题，显然贪心算法是我们最先想到的方法。

那么首先，我们来复习一下什么是贪心算法：

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

—— OI Wiki

接着，我们再来看一眼题目，要想用贪心算法解决问题，我们就需要知道每个子问题的解决方法。如果之于本题，就是探究任意两道题应当如何排序。简单分析可以得到以下结论：

• 对于任意两道题（$a$ & $b$），既可以先做 $a$ 也可以先做 $b$
• 如果先做 $a$，则用时应为 A.s + max(A.g, B.s) + B.g
• 如果先做 $b$，则用时应为 B.s + max(B.g, A.s) + A.g

知道了以上几点，程序自然也就不难了。

三、AC Code

C++

码风较差，将就着看吧

#include <bits/stdc++.h>

using namespace std;

int n;
struct problem {
    int s, g;
} pList[1000000];

bool cmp(problem a, problem b) {
    return a.s + max(a.g, b.s) + b.g < b.s + max(b.g, a.s) + a.g;
}

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> pList[i].s;
        for (int i = 0; i < n; i++) cin >> pList[i].g;
        sort(pList, pList + n, cmp);
        int S = 0, G = 0;
        for (int i = 0; i < n; i++) {
            S += pList[i].s;
            if (G < S) G = S;
            G += pList[i].g;
        }
        cout << G << endl;
    }
    return 0;
}

Python

懒得写排序，先咕着