共有回帖数 0 个
- Off-line Minimum Problem（离线最小值问题）
-
只看楼主
收藏
回复
-
Introduction to Algorithms 中的一道习题
一个包含 n 个 insert 和 m 个 extract-min 操作的序列
insert，插入一个数，这个数来自于域 (1,2,……,n}，，保证每次插入的数互不相同
extract-min，从当前插入且未删除的数中选择最小的输出，然后把这个数删除
希望对一个数组 extracted[1..m] 进行填充，使得 extracted 存放第 i 次 extract-min 操作的结果
比如：
3,5,E,1,2,E,E,E,4,E（整数代表 insert 操作，E 表示 extract-min 操作）
extracted[1..5] 应为
3,1,2,5,4
定义函数
A[k](j) = j+1，若 k = 0
A[k-1]^(j+1) (j)，若 k 0
定义函数
α(n) = min{k : Ak(1) = n}
该问题存在 Ο(nα(n)) 的算法，α(x) 是一个增长极为缓慢的函数，可以近似地看作 Ο(1)
该算法可以近似地看作线性算法
是啊
#include algorithm
#include cstdio
using namespace std;
const int N = 100;
int a[N*2-1], b[N],
id_name[N+1], name_id[N+1],
prev[N+1], next[N+1],
extracted[N], parent[N+1];
int Find(int x)
{
return parent[x] = 0 ? parent[x] = Find(parent[x]) : x;
}
int Union(int x, int y)
{
if (parent[x] parent[y])
return parent[x] += parent[y], parent[y] = x, x;
else
return parent[y] += parent[x], parent[x] = y, y;
}
int main()
{
int m, n;
scanf("%d%d", &n, &m);
for (int cnt = m+n, i = 0, j = 0; cnt; --cnt)
{
scanf("%d", &a);
if (a != -1)
++i;
else
{
if (j && b[j-1] == i)
a[i++] = 0;
b[j++] = i;
}
}
fill_n(parent, n+1, -1);
fill_n(name_id+1, n, m);
id_name[m] = -1;
for (int i = 0; i m; ++i)
{
int curr = !i ? a[0] : b b[i-1] ? a[b[i-1]] : -1;
if (curr != -1)
{
for (int j = i ? b[i-1] : 0; ++j b; )
curr = Union(curr, a[j]);
name_id[curr] = i;
}
id_name = curr;
}
for (int i = 0; i m; ++i)
prev[i+1] = i, next = i+1;
for (int i = 1; i = n; ++i)
{
int name = Find(i), id = name_id[name];
if (id m)
{
if (id_name[next[id]] != -1)
name = Union(name, id_name[next[id]]);
name_id[name] = next[id];
id_name[next[id]] = name;
next[prev[id]] = next[id];
prev[next[id]] = prev[id];
extracted[id] = i;
}
}
for (int i = 0; i m; ++i)
printf("%dn", extracted);
return 0;
}
楼主 2015-12-31 12:59 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
