fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define height 4
  5. #define MAX (1<<height)  //ビットシフト演算 2^height と同じ
  6.  
  7. int t[MAX+1]; //配列外アクセス防止のためのダミーで＋１
  8. int sz = 0;
  9.  
  10. void swap(int *x, int *y){
  11.     int tmp = *x;
  12.     *x = *y;
  13.     *y = tmp;
  14. }
  15.  
  16. void initTree(int n){
  17.     int i;
  18.     for(i=0;i<MAX;i++){
  19.         t[i] = -1;
  20.     }
  21. }
  22.  
  23. void printA(){
  24.     int i;
  25.     for(i=1;i<=sz;i++) printf("%d ",t[i]);
  26.     printf("\n");
  27. }
  28.  
  29. void printT(int i){
  30.     int x = i;
  31.     while(x/2!=0){
  32.         printf("  ");
  33.         x/=2;
  34.     }
  35.     printf("%d\n",t[i]);
  36. }
  37.  
  38. int goP(int i){
  39.     if(i/2 == 0) return 0;
  40.     else return i/2;
  41. }
  42.  
  43. int goL(int i){
  44.     if(2*i >= MAX) return 0;
  45.     else return 2*i;
  46. }
  47.  
  48. int goR(int i){
  49.     if(2*i+1 >= MAX) return 0;
  50.     else return 2*i+1;
  51. }
  52.  
  53. void preOrder(int i){
  54.     if(t[i] == -1) return;
  55.     printT(i);
  56.     preOrder(goL(i));
  57.     preOrder(goR(i));
  58. }
  59.  
  60. void inOrder(int i){
  61.     if(t[i] == -1) return;
  62.     inOrder(goL(i));
  63.     printT(i);
  64.     inOrder(goR(i));
  65. }
  66.  
  67. void postOrder(int i){
  68.     if(t[i] == -1) return;
  69.     postOrder(goL(i));
  70.     postOrder(goR(i));
  71.     printT(i);
  72. }
  73.  
  74. void insBT(int x){
  75.     int k,i = 1;
  76.     for(k=0;k<height;k++){
  77.         if(t[i]==-1){
  78.             t[i] = x;
  79.             sz++;
  80.             return;
  81.         }
  82.         if(x < t[i]) i = goL(i);
  83.         else i = goR(i);
  84.     }
  85.     printf("Error : too high -> %d\n",x);
  86. }
  87.  
  88. //先頭の要素を取り出す
  89. //ダウンヒープ
  90. int popHeap(){
  91.     int i = 1;
  92.     int l,r,ma;
  93.     int ret = t[i];
  94.     t[i] = t[sz]; //t[1] = t[sz]
  95.     t[sz--] = -1; //t[sz]=-1 をしてから sz=sz-1 の意味
  96.     while(i*2 <= sz){
  97.         l = goL(i);
  98.         r = goR(i);
  99.         //子のうち大きい方と比較する
  100.         if(t[l]<t[r]) ma = r;
  101.         else ma = l;
  102.         //子の大きい方と比較して子が大きければ交換する
  103.         //そうでなければヒープ完了．retを返す
  104.         if(t[i] > t[ma]) break;
  105.         swap(&t[i],&t[ma]);
  106.         i = ma;
  107.     }
  108.     return ret;
  109. }
  110.  
  111. //末尾に要素を追加する
  112. //アップヒープ
  113. void pushHeap(int x){
  114.     int i = ++sz;
  115.     int p;
  116.     t[sz] = x;  //余分なダミー要素を作ってあるので配列外アクセスは無い
  117.     while(1<i){
  118.         p = goP(i);
  119.         if(i>=MAX-1) {
  120.             printf("Error : out size < %d -> %d\n",MAX-1,i);
  121.             t[sz] = -1;
  122.             sz--; //要素数が最大を超えていたら追加をしない
  123.             return;
  124.         }
  125.         //親と比較して，今見ている要素（子）の方が小さければ
  126.         //終了する．そうでなければ入れ替えて，続ける
  127.         if(t[i] <= t[p]) return;
  128.         else swap(&t[i],&t[p]);
  129.         i = p;
  130.     }
  131. }
  132. void sort(int a[], int n){
  133. 	int i,j,min;
  134. 	for(i=0;i<n;i++){
  135. 		min=i;
  136. 		for(j=0;j<n;j++){
  137. 			if(a[j]<a[min]){
  138. 				min=j;
  139. 			}
  140. 		}
  141. 		swap(&a[i],&a[min]);
  142. 	}
  143. }
  144.  //必要があれば，関数をいくつでも追加して良い
  145.  
  146. int solve(){
  147.     int ret=0,i,n,q,x;
  148.     int a[50];
  149.     //ここにプログラムを書く
  150.     scanf("%d %d",&n,&q);
  151.     initTree(n);
  152.     for(i=0;i<n;i++){
  153.     	scanf("%d",&a[i]);
  154.     }
  155.     sort(a,n);
  156.     for(i=0;i<n;i++){
  157.     	pushHeap(a[i]);
  158.     }
  159.     for(i=0;i<q;i++){
  160.     	pushHeap(popHeap()/2);
  161.     }
  162.     for(i=1;i<=sz;i++){
  163.     	ret+=t[i];
  164.     }
  165.     return ret;
  166. }
  167.  
  168. //メイン関数はいじらなくて良い
  169. int main(void){
  170.     printf("%d\n",solve());
  171.     return 0;
  172. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
7 2
10 40 60 30 80 5 30
stdout
copy 
185
https://ideone.com/jV8szQ
language:
C (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!