花茶网站设计,网站底部浮动电话广告,wordpress仿国际,南坪网站建设哪里好[蓝桥杯 2020 省 A1] 超级胶水
题目描述
小明有 n n n 颗石子#xff0c;按顺序摆成一排#xff0c;他准备用胶水将这些石子粘在一起。
每颗石子有自己的重量#xff0c;如果将两颗石子粘在一起#xff0c;将合并成一颗新的石子#xff0c;重量是这两颗石子的重量之和…[蓝桥杯 2020 省 A1] 超级胶水
题目描述
小明有 n n n 颗石子按顺序摆成一排他准备用胶水将这些石子粘在一起。
每颗石子有自己的重量如果将两颗石子粘在一起将合并成一颗新的石子重量是这两颗石子的重量之和。
为了保证石子粘贴牢固粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比本题不考虑物理单位认为所需要的胶水在数值上等于两颗石子重量的乘积。
每次合并小明只能合并位置相邻的两颗石子并将合并出的新石子放在原来的位置。
现在小明想用最少的胶水将所有石子粘在一起请帮助小明计算最少需要多少胶水。
输入格式
输入的第一行包含一个整数 n n n表示初始时的石子数量。
第二行包含 n n n 个整数 w 1 , w 2 , ⋯ , w n w_1, w_2, \cdots, w_n w1,w2,⋯,wn 依次表示每颗石子的重量。
输出格式
输出一行包含一个整数表示最少需要的胶水数。
样例 #1
样例输入 #1
3
3 4 5样例输出 #1
47样例 #2
样例输入 #2
8
1 5 2 6 3 7 4 8样例输出 #2
546提示
对于 20 % 20\% 20% 的评测用例 1 ≤ n ≤ 15 1 \le n \le 15 1≤n≤15。
对于 60 % 60\% 60% 的评测用例 1 ≤ n ≤ 100 1\leq n \leq 100 1≤n≤100。
对于 80 % 80\% 80% 的评测用例 1 ≤ n ≤ 1000 1\leq n \leq 1000 1≤n≤1000。
对于所有评测用例 1 ≤ n ≤ 1 0 5 1\leq n \leq 10^5 1≤n≤105 1 ≤ w i ≤ 1000 1 \leq w_i \leq 1000 1≤wi≤1000。
蓝桥杯 2020 第一轮省赛 A 组 I 题。 思路
首先将所有的石子重量读入存入一个最小堆优先队列中。优先队列的特性是每次取出的都是队列中最小的元素。
然后利用贪心算法每次都选择最小的两颗石子进行粘合这样可以保证所需的胶水最少。每次从优先队列中取出两个最小的石子将这两颗石子粘在一起形成一颗新的石子新石子的重量是这两颗石子的重量之和所需的胶水是这两颗石子的重量的乘积。将新石子的重量再次放入优先队列中同时将所需胶水累加到总胶水量中。
重复以上步骤直到优先队列中只剩下一颗石子这时候所有的石子都已经粘在一起总胶水量即为所求。 AC代码
#include algorithm
#include iostream
#include queue
#include vector
#define mp make_pair
#define AUTHOR HEX9CF
using namespace std;
using ll long long;const int N 1e6 7;
const int INF 0x3f3f3f3f;
const ll MOD 1e9 7;int n;
priority_queuell, vectorll, greaterll hmin;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;while (n--) {int t;cin t;hmin.push(t);}ll ans 0;while (hmin.size() 1) {ll a hmin.top();hmin.pop();ll b hmin.top();hmin.pop();ll c a b;ans a * b;hmin.push(c);}cout ans;return 0;
}
