今天是2019.5.21 距离NOIP2019还有171天
今天做了一道合并果子
看之前洛谷提交记录只得了10分？？！
今天重新做了一下
题是中文的 就不解读了 用了贪心
每一次都将最小的两堆合并即可
所以我就开始xjbx就排了一次序然后从小加到大
显然不对 因为合并后的一堆果子质量并不一定是最小的
但每一次都sort显然会超时
所以我就想到了STL里的优先队列
(然而我忘记了代码怎么写)
看看詹爷的合并果子题解慢慢回忆才想起来
上代码
#include<cstdio> #include<cstring> #include<cmath> #include<cctype> #include<cstdlib> #include<string> #include<iostream> #include<algorithm> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #define enter puts("") #define space putchar(' ') using namespace std; typedef long long ll; int read() { int op = 1, ans = 0; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = 0; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return op ? ans : -ans; } void write(int x) { if(x < 0) { x = -x; putchar('-'); } if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } priority_queue<int, vector<int>, greater<int> >q; int n, ans; int main() { n = read(); for(int i = 1;i <= n;i++) { int xz = read(); q.push(xz); } for(int i = 1;i < n;i++) { int a = q.top(); q.pop(); int b = q.top(); q.pop(); ans += a + b; q.push(a + b); } write(ans); enter; return 0; }