自动搬运

查看原文

来自洛谷，原作者为

	SuperJvRuo **

搬运于2025-08-24 21:54:05，当前版本为作者最后更新于2018-04-15 08:28:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不难发现，同一动作，无论进行几次，其能带来的价值都是$c_i*$(最后一次进行的时间-首次进行的时间)

因此此题的本质是设计方案使得$\sum_{i=1}^kc_i*$(最后一次进行的时间-首次进行的时间)最大

贪心，让$c$大的动作相隔时间最长，尽可能地安排在两端，即可得到最优解

#include<cstdio>
#include<algorithm>
#include<functional>

int a[1005];

int main()
{
    int n, k;
    int ans = 0;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < k; i++)
        scanf("%d", &a[i]);
    std::sort(a, a+k, std::greater<int>());
    n--;
    int i = 0;
    while(n > 0 && i < k)
    {
        ans += n*a[i];
        i++;
        n-=2;
    }
    printf("%d\n", ans);
    return 0;
}