Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 谁帮我看看思路（最小堆）

Posted by TYplayIT at 2011-12-02 11:10:38 on Problem 2051
```输入完num和period之后建立最小堆，

#include<iostream>

using namespace std;

typedef struct
{
int num;
int p, op;
}Ins;

void MakeHeap(Ins a[], int n);
void addIns(Ins a[], int n, Ins b);
void FixUp(Ins a[],int i, int n);

Ins deleteIns(Ins a[], int n);
void FixDown(Ins a[], int i, int n);
void swap(Ins &a, Ins &b);

int main()
{
char input[20];
Ins a[2020];
int n;
int i = 0;
while( cin >> input)
{
if(input[0] == '#')
{
break;
}
cin >> a[i].num >> a[i].p;
a[i].op = a[i].p;
i++;
}

cin >> n;

MakeHeap(a, i);
Ins temp;
for(int j = 0; j < n; j++)
{
temp = deleteIns(a, i);
for(int k = 0; k < i-1; k++)
{
a[k].p -= temp.p;
}
cout << temp.num << endl;
temp.p = temp.op;
}
return 0;
}

void MakeHeap(Ins a[], int n)       //n为数组个数
{
for(int i = n/2-1; i > -1; i--)
{
FixDown(a, i, n);
}
}
void addIns(Ins a[], int n, Ins b)      //n为添加前数组个数
{
a[n] = b;
FixUp(a, n, n+1);
}
void FixUp(Ins a[],int i, int n)        //i为新添加元素的位置，n为当前数组个数
{
for(; i > 0; i /= 2)
{
if(a[i].p < a[i/2].p)
{
swap(a[i], a[i/2]);
}
else if(a[i].p == a[i/2].p)
{
if(a[i].num < a[i/2].num)
{
swap(a[i], a[i/2]);
}
}
}
}
Ins deleteIns(Ins p[], int n)       //n为当前数组个数
{
Ins temp = p[0];
p[0] = p[n-1];
FixDown(p, 0, n-1);
return temp;
}
void FixDown(Ins a[], int i, int n)     //i为下移的元素位置，n为当前个数
{
int j = i*2 +1;
Ins temp = a[i];
while( j < n)
{
if(j+1 < n)
{
if(a[j].p > a[j+1].p)
{
j++;
}
else if(a[j].p == a[j+1].p && a[j].num > a[j+1].num)
{
j++;
}
}
if(a[j].p > temp.p)
{
break;
}
else if(a[j].p == temp.p && temp.num < a[j].num)
{
break;
}
a[i] = a[j];
i = j;
j = j * 2 +1;
}
a[i] = temp;
}
void swap(Ins &a, Ins &b)
{
Ins temp = a;
a = b;
b = temp;
}
```

Followed by: