我才不是萝莉控呢

Description

小Y：“小R 你是萝莉控吗。”小R：“…”
为了避免这个尴尬的话题，小R 决定给小Y 做一道题。
有一个长度为n 的正整数数组A，满足Ai >= Ai+1，现在构造一个数组B，令Bi =。
现在，有一个n * n 的网格图，左下角坐标是(1, 1)，右上角坐标是(n, n)。有一个小SB正在坐标为(n, 1) 的位置，每一时刻，如果他现在在(x, y)，他可以选择走到(x -1,y + 1) 或者(x, (y + 1) div 2)，如果选择后者，他要支付Bx的代价。
现在他想走到(1, 1)，你可以告诉他他支付的代价最少是多少吗？注意在任何时候他都不能离开这个网格图。

Input

第一行输入一个正整数T 表示数据组数。
对于每组数据，第一行是一个整数n，接下来一行n 个整数表示数组A。

Output

对于每组数据，输出一个整数表示答案。

Sample Input

1
3
1 1 1

Sample Output

样例解释：
选择的路径可以是：(3， 1)->(2， 2)->(2， 1)->(1， 2)->(1， 1)

Data Constraint

对于30% 的数据，n <= 10
对于50% 的数据，n <=1000
对于100% 的数据，n<= 10^5，1 <= T<= 10，1 <= Ai<= 10^4

.
.
.
.
.
分析
这题其实是哈夫曼树
但其模拟出来的过程与合并果子的做法类似。
所以正解可以是合并果子(滑稽)
感性理解

.
.
.
.
.
程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

priority_queue<int,vector<int>,greater<int> >q;

int main()
{
 int t;
 scanf("%d",&t);
 while (t--)
 {
  int n;
  scanf("%d",&n);
  long long ans=0;
     for (int i=1,x;i<=n;i++) 
  {
   scanf("%d",&x);
   q.push(x);
  }
        for (int i=n,x;i>1;i--) 
        {
         x=q.top();
   q.pop();
   x+=q.top();
   q.pop();
   ans+=x;
   q.push(x);
  }
        printf("%lld\n",ans);
        while (!q.empty()) q.pop();
 }
 return 0;
}

我才不是萝莉控呢

浏览过的版块