domino

题意：

问题描述

小白在玩一个游戏。桌子上有n张多米诺骨牌排成一列。它有k次机会，每次可以选一个还没有倒的骨牌，向左或者向右推倒。每个骨

牌倒下的时候，若碰到了未倒下的骨牌，可以把它推倒。小白现在可以随意设置骨牌的高度，但是骨牌高度为整数，且至少为1，并且

小白希望在能够推倒所有骨牌的前提下，使所有骨牌高度的和最小。

输入描述

第一行输入一个整数T

每组数据有两行

第一行有两个整数n和k，分别表示骨牌张数和机会次数。

第二行有n-1个整数，分别表示相邻骨牌的距离d

输出描述

对于每组数据，输出一行，最小的高度和

输入样例

1

4 2

2 3 4

输出样例

9

题解：

首先这么想，肯定是距离越远，就越要用那k-1次去推，最后用1次把所有都推了就好了，所以是先sort一遍，倒着处理就好了，有浓厚的贪心味道。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const ll LINF=0x3f3f3f3f3f3f3f3f;

#define PU puts("");

#define PI(A) cout<<A<<endl

#define SI(N) cin>>N

#define SII(N,M) cin>>N>>M

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

#define dbg(x) cout <<#x<<" = "<<x<<endl

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 100000 + 9 ;

int k,n;

int a[MAXN];

int main()

{

    iostream::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    int o;

    SI(o);

    while(o--)

    {

        SII(n,k);

        rep(i,n-1) SI(a[i]);

        sort(a,a+n-1);

        ll ans=0;

        reRep(i,n-2,0)

        {

            k--;

            if (k>=1)

                ans++;

            else

                ans+=a[i]+1;

        }

        ans+=1;

        PI(ans);

    }

    return 0;

}

巴特西

BestCoder Round #85 hdu5777 domino

domino

题意：

题解：

代码：

最新文章

热门文章