题解 P3918 【[国家集训队]特技飞行】

SuperJvRuo · 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;
}