分类目录归档：堆

PTA 团体程序设计天梯赛-练习集 L2-012 关于堆的判断

发表评论

这道题里坑点很大：反而不利于深入学习过数据结构的同学做题。。
先贴代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<map>
#include<string>
#include<functional>
#include<algorithm>
#include<stack>
#include<list>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
//Root is 1
//小顶堆
int n, m;
int heap[1005];
int Hsize = 0;
inline int lson(int x) {
    return x * 2;
}
inline int rson(int x) {
    return x * 2 + 1;
}
inline int father(int x) {
    return x / 2;
}
void PercolateUp(int node) {
    if (heap[node] < heap[father(node)]) {
        swap(heap[node], heap[father(node)]);
        PercolateUp(father(node));
    }
}
void insert(int x) {
    heap[++Hsize] = x;
    PercolateUp(Hsize);
}
int _findNode(int v) {
    for (int i = 1; i <= n; i++) {
        if (v == heap[i])return i;
    }
    return -1;
}
bool isRoot(int v) {
    return heap[1] == v;
}
bool isSiblings(int v1, int v2) {
    int node = _findNode(v1);
    if (node % 2 == 1)return heap[node - 1] == v2;
    else return heap[node + 1] == v2;
}
bool isParent(int C,int F){
    int node = _findNode(C);
    return heap[father(node)] == F;
}
bool isChild(int C, int F) {
    int node = _findNode(F);
    return heap[lson(node)] == C || heap[rson(node)] == C;
}
int Itype; //0 root,1 sibling,2 parent,3 child
int Ix, Iy;
char str[100];
void getInput() {
    scanf("%d", &Ix);
    scanf("%s", str);
    if (strcmp(str, "and") == 0) {
        Itype = 1;
        scanf("%d", &Iy);
        scanf("%s", str);
        scanf("%s", str);
        return;
    }
    scanf("%s", str);
    if (strcmp(str, "a") == 0) {
        Itype = 3;
        scanf("%s", str);
        scanf("%s", str);
        scanf("%d", &Iy);
        return;
    }
    scanf("%s", str);
    if (strcmp(str, "root") == 0) {
        Itype = 0;
        return;
    }
    Itype = 2;
    scanf("%s", str);
    scanf("%d", &Iy);
    return;
}
int main() {
    heap[0] = -100000;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        insert(x);
    }
    for (int i = 1; i <= m; i++) {
        getInput();
        bool flag;
        switch (Itype) {
        case 0:flag = isRoot(Ix); break;
        case 1:flag = isSiblings(Ix, Iy); break;
        case 2:flag = isParent(Iy, Ix); break;
        case 3:flag = isChild(Ix, Iy); break;
        }
        cout << (flag ? "T" : "F")<< endl;
    }
}

对我来说的坑点：一个是数据范围是有负数的！！！还有一个，儿子、父亲节点不是广义儿子、父亲节点，只是直属的，有直接相连边的，间接连接的不算，还有一个是不能使用一次全部读入到数组里从n/2下标到n一起上滤的做法，必须插入一个，上滤一次，这种算法很辣鸡。

洛谷 P1631 序列合并

发表评论

思路完全同P2085，用大根堆，如果比堆顶小，就把堆顶的换下来，比堆顶大就扔掉不要break。
这种思路看起来很好用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
priority_queue<ll> pq;
stack<ll> s;
ll n, A[100005], B[100005];
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> A[i];
    for (int i = 1; i <= n; i++)cin >> B[i];
    for (int i = 1; i <= n; i++) {
        pq.push(A[1] + B[i]);
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (pq.top() > A[i] + B[j]) {
                pq.pop();
                pq.push(A[i] + B[j]);
            }
            else break;
        }
    }
    while (!pq.empty()) {
        s.push(pq.top());
        pq.pop();
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

洛谷 P2085 最小函数值

发表评论

有点不好做，先得知道二次函数的性质，最小值是x=-b/2a。然后用堆的时候要小心，要用大根堆，一次性把堆加满，探测每个二次函数轴附近的值是否比堆里的最大值大，如果是的话就把堆里的最大值取出来，不是的话就可以终止这次二次函数的循环了。最后因为是大根堆，用个栈把顺序颠倒过来再输出就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
int A[10005], B[10005], C[10005];
priority_queue<int> pq;
stack<int> s;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)pq.push(0x7fffffff);
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i] >> C[i];
        double pivot = -1.0*B[i] / 2 / A[i];
        if (pivot < 0) {
            for (int j = 1; j <= m; j++) {
                int v = A[i] * j*j + B[i] * j + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else break;
            }
        }
        else {
            int p = round(pivot);
            int v = A[i] * p * p + B[i] * p + C[i];
            if (v < pq.top()) {
                pq.pop();
                pq.push(v);
            }
            for (int j = 0; 2 * j <= m - 1; j++) {
                bool flag = true;
                v = A[i] * (p + j + 1)*(p + j + 1) + B[i] * (p + j + 1) + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else flag = false;
                v = A[i] * (p - j - 1)*(p - j - 1) + B[i] * (p - j - 1) + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else flag = false;
                if (!flag)break;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        s.push(pq.top());
        pq.pop();
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

洛谷 P1801 黑匣子_NOI导刊2010提高（06）

发表评论

异常清晰，自己花了好长时间想出来的，继续加油！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
struct BlackBox {
private:
    priority_queue<ll,vector<ll>,greater<ll> > minHeap;
    priority_queue<ll> maxHeap;
public:
    void add(ll num) {
        if (maxHeap.empty())minHeap.push(num);
        else if (num < maxHeap.top()) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            maxHeap.push(num);
        }
        else minHeap.push(num);
    }
    ll get() {
        ll re = minHeap.top();
        maxHeap.push(minHeap.top());
        minHeap.pop();
        return re;
    }
}BB;
int m, n;
ll arr1[200005], arr2[200005];
ll arr2Ptr = 1;
int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) cin >> arr1[i];
    for (int i = 1; i <= n; i++)cin >> arr2[i];
    for (int i = 1; i <= m; i++) {
        BB.add(arr1[i]);
        while (arr2[arr2Ptr] == i) {
            cout << BB.get() << endl;
            arr2Ptr++;
        }
    }
}

数据结构 邓俊辉 PA#4 任务调度(Schedule)题解

发表评论

任务调度(Schedule)

Description

A HPS cluster is equipped with a unique task scheduler. To be simple, it is assumed that this cluster doesn’t support multiple tasks running at the same time, such that only one task is allowed to be in running state at any moment. Initially, the priority of ever task is denoted by an integer which is called priority number. The smaller priority number stands for high priority. If two tasks have same task number, the priority is decided in the ASCII order of task name. Following this policy, resources, such as CPU, are always occupied by the task with minimum priority number. When one task is finished, the one with minimum priority number in the rest tasks is picked to execute. The finished task won’t quit immediately. The priority number is doubled and put back to the task set. Once the priority number is greater or equal to 2^32, this task is deleted from the task set.

Given initial priority setting of every task, your job is to predict the running order of a batch of tasks.

Input

First line contains two integers, says n and m. n stands for the number of tasks in initial state. m stands for the length of predicted sequence. Every line is ended by a line break symbol. In each one of the following n lines, an integer and a string are included. This string is shorter than 8, which only contains lowercase letters and numbers. The integer is priority number and the string is the task name. The integer and string is separated by space.

Output

At most m lines, each one contains a string. Output the name of tasks according to the order that tasks are executed. If the number of executed tasks is less than m, then output all the executed tasks.

Example

Input

3 3
1 hello
2 world
10 test

Output

hello
hello
world

Restrictions

0 <= n <= 4,000,000

0 <= m <= 2,000,000

0 < Priority number < 2^32

No tasks have same name

Time: 2 sec

Memory: 512 MB

Hints

Priority queue

描述

某高性能计算集群（HPC cluster）采用的任务调度器与众不同。为简化起见，假定该集群不支持多任务同时执行，故同一时刻只有单个任务处于执行状态。初始状态下，每个任务都由称作优先级数的一个整数指定优先级，该数值越小优先级越高；若优先级数相等，则任务名ASCII字典顺序低者优先。此后，CPU等资源总是被优先级数最小的任务占用；每一任务计算完毕，再选取优先级数最小下一任务。不过，这里的任务在计算结束后通常并不立即退出，而是将优先级数加倍（加倍计算所需的时间可以忽略）并继续参与调度；只有在优先级数不小于2^32时，才真正退出

你的任务是，根据初始优先级设置，按照上述调度原则，预测一批计算任务的执行序列。

输入

第一行为以空格分隔的两个整数n和m，n为初始时的任务总数，m为所预测的任务执行序列长度，每行末尾有一个换行符

以下n行分别包含一个整数和一个由不超过8个小写字母和数字组成的字符串。前者为任务的初始优先级数，后者为任务名。数字和字符串之间以空格分隔

输出

最多m行，各含一个字符串。按执行次序分别给出执行序列中前m个任务的名称，若执行序列少于m，那么输出调度器的任务处理完毕前的所有任务即可。

样例

见英文题面

限制

0 ≤ n ≤ 4,000,000

0 ≤ m ≤ 2,000,000

0 < 每个任务的初始优先级 < 2^32

不会有重名的任务

时间：2 sec

内存：512 MB

提示

优先级队列

必须要用坑爹的setvbuf:
继续阅读 →