T1 排排坐

题意概括

---

有 $n$ 个小朋友，每个人手上写了一个正整数 $a_i$。

老师发糖果时，第 $i$ 个位置的小朋友可以获得：

❝ 自己以及左侧所有小朋友手上数字之和

也就是这一排到当前位置的前缀和。

现在可以重新安排小朋友的位置，要求所有小朋友获得糖果总量最大。

思路分析

---

假设最终排列为：
$b_1,b_2,...,b_n$
那么总糖果数为：
$b_1+(b_1+b_2)+(b_1+b_2+b_3)+...+(b_1+b_2+...+b_n)$
把每个数出现的次数整理一下：

• List item
• $b_1$会被加 $n$ 次；
• $b_2$会被加 $n-1$ 次；
• $b_3$会被加 $n-2$ 次；
• $...$
• $b_n$会被加 1 次。

所以总糖果数为：

$$n\times b_1+(n-1)\times b_2+\dots +1\times b_n$$

前面的系数更大，因此应该把大的数字放在前面。

所以最优策略是：

然后按排序后的顺序计算前缀和总和即可。

复杂度分析

排序复杂度为：$O(n\log n)$

计算答案复杂度为：$O(n)$

总复杂度：$O(n\log n)$

参考代码

---

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1005;

int n;
ll a[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1, greater<ll>());
    ll sum = 0;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        sum += a[i];
        ans += sum;
    }
    cout << ans << '\n';

    return 0;
}

T2 晚宴

题意概括

---

给定 $n$ 个正整数，从中选出两个数，要求这两个数互质。

在所有满足条件的选择中，求这两个数的最大和。

两个数互质，指它们的最大公因数为 $1$。

也就是：$\gcd (a_i,a_j)=1$

思路分析

---

数据范围：
$$2\le n\le 1000$$
所以可以直接枚举任意两个数。

一共有：
$$\frac{n(n-1)}{2}$$

对数，最多约为 $5\times 10^5$ 对。

每一对用 gcd 判断是否互质即可。

如果：

__gcd(a[i], a[j]) == 1

说明这两个数互质，就用它们的和更新答案。

复杂度分析

枚举数对复杂度：$O(n^2)$

每次求最大公因数复杂度约为：$O(\log V)$，其中 $V$ 是数字大小。

所以总复杂度为：$O(n^2\log V)$，对于 $n\le 1000$ 完全可以通过。

参考代码

---

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;

int n;
int a[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(__gcd(a[i], a[j]) == 1){
                ans = max(ans, a[i] + a[j]);
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

小优化写法

也可以先从大到小排序，这样越靠前的数越大。如果当前两数之和已经不可能超过答案，就可以提前跳过一些情况。不过因为 $n\le 1000$，普通 $O(n^2)$ 已经足够，不需要复杂优化。