深圳公司网站开发,企业网站空间在哪里,上海城乡建设网站,宣传片制作标准参数1 // 两个队列k叉哈夫曼树 HDU 58842 // camp题解#xff1a;3 // 题意#xff1a;nn个有序序列的归并排序.每次可以选择不超过kk个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过TT, 问kk最小是多少。4 // .5 // 题解#xff1a;首先二分一下这个kk。然后在… 1 // 两个队列k叉哈夫曼树 HDU 58842 // camp题解3 // 题意nn个有序序列的归并排序.每次可以选择不超过kk个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过TT, 问kk最小是多少。4 // .5 // 题解首先二分一下这个kk。然后在给定kk的情况下这个代价其实就是kk叉的哈夫曼树问题。因此直接套用哈夫曼树的堆做法即可。复杂度O(nlog^2n)6 // 这样优化一下读入是可以卡过去的。7 // 然后主代码手表示利用合并的单调性可以去掉优先队列得到O(nlogn)的做法先对所有数排序另外一个队列维护合并后的值取值时从两个序列前端取小的即可。8 // 昂如果(n-1)%(k-1)≠0要把最小的(n-1)%(k-1)1个数先合并一下。9
10 #include iostream
11 #include algorithm
12 #include cstring
13 #include cstdio
14 #include vector
15 #include cmath
16 #include map
17 #include queue
18 using namespace std;
19 #define LL long long
20 typedef pairint,int pii;
21 const int inf 0x3f3f3f3f;
22 const int MOD 998244353;
23 const int N 1e510;
24 const int maxx 200010;
25 #define clc(a,b) memset(a,b,sizeof(a))
26 const double eps 1e-8;
27 void fre() {freopen(in.txt,r,stdin);}
28 void freout() {freopen(out.txt,w,stdout);}
29 inline int read() {int x0,f1;char chgetchar();while(ch9||ch0) {if(ch-) f-1; chgetchar();}while(ch0ch9) {xx*10ch-0;chgetchar();}return x*f;}
30
31 int a[N];
32 int n,m;
33 bool check(int k){
34 queueLLq1;
35 queueLLq2;
36 if((n-1)%(k-1)!0){
37 for(int i1;ik-1-(n-1)%(k-1);i)
38 q1.push(0);
39 }
40 for(int i1;in;i){
41 q1.push(a[i]);
42 }
43 LL sum0;
44 while(1){
45 LL tem0;
46 for(int i1;ik;i){
47 if(q1.size()0q2.size()0) break;
48 int a1,a2;
49 if(q1.size()0){
50 temq2.front();
51 q2.pop();
52 continue;
53 }
54 if(q2.size()0) {
55 temq1.front();
56 q1.pop();
57 continue;
58 }
59 a1q1.front();
60 a2q2.front();
61 if(a1a2) {tema1;q1.pop();}
62 else {tema2;q2.pop();}
63 }
64 sumtem;
65 if(q1.size()0q2.size()0) break;
66 q2.push(tem);
67 }
68 if(summ) return false;
69 else return true;
70 }
71
72 int main(){
73 // fre();
74 int T;
75 scanf(%d,T);
76 while(T--){
77 scanf(%d%d,n,m);
78 for(int i1;in;i) scanf(%d,a[i]);
79 sort(a1,a1n);
80 int l2,rn;
81 while(lr){
82 int mid(lr)1;
83 if(check(mid)) rmid;
84 else lmid1;
85 }
86 printf(%d\n,r);
87 }
88 return 0;
89 } 转载于:https://www.cnblogs.com/ITUPC/p/5880773.html
