牛客2020寒假训练营2-H

牛客2020寒假训练营2-H

七月 15, 2020

H.释魔法

题意
牛可乐有 n 个元素( 编号 1..n )，第 i 个元素的能量值为 ai。 牛可乐可以选择至少 k 个元素来施放一次魔法，魔法消耗的魔力是这些元素能量值的极差。形式化地，若所用元素编号集合为 S，则消耗的魔力为 max ⁡i∈S{ai}−min ⁡i∈S{ai}

牛可乐要求每个元素必须被使用恰好一次。 牛可乐想知道他最少需要多少魔力才能用完所有元素。

题解

首先将元素按能量值排序
dp i表示用掉前i个元素的最小代价
dp i=min (1<=j<=i-k+1) {dp [j-1]+ ai - aj} =min (..) {dp [j-1] -aj} +ai;
维护 dp[j-1] -aj的最小前缀 O1转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll dp[(int)3e5+5];
ll data[(int)3e5+5];
const ll maxn=(ll)1e9+4;
int main(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>data[i];
    sort(data+1,data+n+1);
    ll per=-data[1];///初始化最开始2k个都是由它来更新
    for(int i=1;i<k;i++)dp[i]=maxn;///前k-1个不满足至少k个元素的要求
    for(int i=k;i<=n;i++){
        dp[i]=per+data[i];///大于k个作为一组需消耗data[i]-data[1]
        per=min(per,dp[i-k+1]-data[i-k+2]);
        ///为下个dp i+1更新 计算per, 那么对于右端点i+1他的左端点就最大就是i-k+2,上一个区间的右端点就是i-k+1
    }
    cout<<dp[n]<<endl;
}