#include <stdio.h>
#define LEFT_CHILD(x) (2*x + 1)
#define RIGHT_CHILD(x) (2*x + 2)
#define PARENT(x) ((x-1)/2)
#define SWAP(a,b) {int t; t = a; a=b; b=t;}
void HeapSort(int *base, int n);
void InitHeap(int *base, int n);
void MakeHeap(int *base, int n);
void HeapSort(int *base, int n)
{
int on = n;
InitHeap(base, n);
n--;
SWAP(base[0], base[n]);
while (n>1)
{
MakeHeap(base, n);
n--;
SWAP(base[0], base[n]);
}
}
void InitHeap(int *base, int n)
{
int pa = 0;
int now;
int i;
for (i = 1; i<n; i++)
{
now = i;
while (now>0)
{
pa = PARENT(now);
if (base[now]>base[pa])
{
SWAP(base[now], base[pa]);
now = pa;
}
else
{
break;
}
}
}
}
int FindMaxIndex(int *base, int n, int now);
void MakeHeap(int *base, int n)
{
int now = 0;
int mp = 0;
while (LEFT_CHILD(now) < n)
{
int mp = FindMaxIndex(base, n, now);
if (mp == now)
{
break;
}
SWAP(base[mp], base[now]);
now = mp;
}
}
int FindMaxIndex(int *base, int n, int now)
{
int lc = LEFT_CHILD(now);
int rc = RIGHT_CHILD(now);
if (rc >= n)
{
if (base[now]<base[lc])
{
return lc;
}
return now;
}
if (base[lc]<base[rc])
{
return rc;
}
return lc;
}
void ViewArr(int *arr, int n)
{
int i = 0;
for (i = 0; i<n; i++)
{
printf("%2d ", arr[i]);
}
printf("\n");
}
int main()
{
int N, K, i, j = 1, k = 1;
long long result = 0;
int temp = 0, prev = 0;
int *arr;
scanf("%d %d", &N, &K);
arr = (int*)malloc(sizeof(int)*N);
for (i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
HeapSort(arr, N);
ViewArr(arr, N);
for (i = 1; i <= K; i++) {
if (i % 2 == 1) {
if (i == 1) {
temp = arr[N - i];
result += temp;
}
else {
temp = arr[N - i + k];
result += temp - prev;
k++;
}
}
else {
prev = arr[i - (j + 1)];
j++;
}
}
printf("%lld", result);
}
Compilation message
wine.c: In function 'HeapSort':
wine.c:14:6: warning: unused variable 'on' [-Wunused-variable]
int on = n;
^
wine.c: In function 'MakeHeap':
wine.c:55:6: warning: unused variable 'mp' [-Wunused-variable]
int mp = 0;
^
wine.c: In function 'main':
wine.c:105:14: warning: implicit declaration of function 'malloc' [-Wimplicit-function-declaration]
arr = (int*)malloc(sizeof(int)*N);
^
wine.c:105:14: warning: incompatible implicit declaration of built-in function 'malloc'
wine.c:105:14: note: include '<stdlib.h>' or provide a declaration of 'malloc'
wine.c:104:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &K);
^
wine.c:107:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &arr[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
