题目意思很简单,就是说,给了你 n 个堆,每个堆有一个重量,现在要把这 n 个堆合并成一个堆,问怎么合并是的合并的花费最少,合并的花费是这样定义的:A 堆合并到 B 堆上,那么本次合并的花费就是 A 堆的重量。但是这样出题人觉得太简单了,于是就规定每一堆最多只能被合并 k 次
初一看感觉很神,完全没思路
反省:
想问题的时候不要脱离题目,注意题目的限制条件,画画图,抓住题目的性质,这样就不容易卡题了,再神的题也是出出来做的,总是能够想到方法的,现在自己会的方法已经很多了,还担心刷不了神题?自信点,不要把简单的事情想复杂,要学会思考,不要盯着题目发神。
解题思路:
思想是贪心,至于怎么贪,我们来看看题目给的限制条件:
1、每堆只能被合并 k 次
2、每一堆只能合并一次
注意到这里,我们不难发现,堆与堆之间的关系实际上就构成了一棵树:每个节点表示一个堆,再给个权值(对应堆的重量),每个节点有不多于 k 个子树,合并的过程就是从叶子节点依次向上合并,这样就把题目成功的转化了
接下来就是怎么建树,使得合并产生的花费最少了,根据合并产生花费的方式,不难想到一下两点:
1、 每个节点的子树应该尽量靠近k
2、 距离根的距离越远的层,那一层的权值和应该越小
这样,贪心的策略就出来了
具体实现的时候其实不必建一棵树,我们只需要知道这是一棵树就行了,知道这棵树的第I 层包含哪些节点,这些节点的权值和是多少就完了
#include <cstdio> #include <cstring> #include <cstdlib> #include <ctime> #include <cmath> #include <iostream> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <list> #include <algorithm> using namespace std; typedef long long LL; typedef double DB; typedef unsigned long long ULL; typedef unsigned int Uint; const int INT_INF=0x3fffffff; const LL LL_INF=0x3fffffffffffffff; const DB EPS=1e-9; const DB PI=3.14159265358979323846; const int N=100010; const int E=100010; #define PB push_back #define MP make_pair #define MH make_heap #define PH push LL a[N]; LL s[N]; LL ans[N]; bool cmp(LL a,LL b) { return a>b; } int main() { LL n , m; while(~scanf("%I64d",&n)) { for(int i=1; i<=n; i++) scanf("%I64d",a+i); sort(a+1,a+1+n,cmp); memset(s,0,sizeof(s)); for(int i=1; i<=n; i++) s[i]=s[i-1]+a[i]; memset(ans,-1,sizeof(ans)); scanf("%I64d",&m); for(int ca=0, val; ca<m; ca++) { scanf("%d",&val); if(val>n) val=n; if(ans[val]==-1) { ans[val]=0; for(LL L=1, R=L+val, step=val, deep=1; L<n; L=R, deep++, step*=val) { R=L+step; if(R>n) R=n; ans[val]+=deep*(s[R]-s[L]); } } printf("%I64d",ans[val]); if(ca==m-1) printf("\n"); else printf(" "); } } return 0; }