【杭电】[5777]domino - BoilTask's Blog

问题描述

domino

问题分析

中文题意：

小白在玩一个游戏。桌子上有n张多米诺骨牌排成一列。它有k次机会，每次可以选一个还没有倒的骨牌，向左或者向右推倒。每个骨牌倒下的时候，若碰到了未倒下的骨牌，可以把它推倒。小白现在可以随意设置骨牌的高度，但是骨牌高度为整数，且至少为1，并且小白希望在能够推倒所有骨牌的前提下，使所有骨牌高度的和最小。

官方题解：

首先骨牌只要考虑都往右推，其次能带倒骨牌的前提是高度大于等于距离+1。
所以如果推一次，那么就是骨牌高度=离下一块骨牌距离+1. 把第一块左边距离设为无穷大，能推nk次，那么就是找nk块左边距离最大的向右推倒即可，所以只需要排序找到前nk-1大的距离。
有个小trick，推的次数可能大于骨牌数量复杂度 O（nlogn）

由题意可知需要尽量使距离大的浪费掉
所以把累加（距离+1）再尽量减去最大距离
就可以取得最小高度

PS：注意数据范围 int 存不下sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b) {
    return a>b;
}
__int64 a[100200];
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n,k;
        scanf("%d %d",&n,&k);
        n--;
        __int64 sum=0;
        for(int i=0; i<n; i++) {
            scanf("%I64d",&a[i]);
            sum+=a[i]+1;
        }
        sum++;
        sort(a,a+n,cmp);
        for(int i=0; i<k-1&&i<n; i++)
            sum=sum-a[i];
        printf("%I64d\n",sum);
    }
    return 0;
}