BOJ 1295 ACM system 【可修改堆】

ACM system
Login and star it!
Submit: 283   Accepted:39
Time Limit: 3000MS  Memory Limit: 65535K
Description
912实验室最近设计了一种能够自动控制进程调度的系统,英文名是Automatic Control Machinery,简称ACM。该系统具有很多优秀的功能,为了方便大家的理解,这里先介绍一下关于进程、进程调度的常识。
1、 每个进程需要占用1个或多个单位内存空间,然而令人惊叹的是,在912实验室开发的平台上,一个进程只需要占用1个单位内存!
2、 每个进程用三个参量来表示,编号、权值、内存地址(0x00000000~0xFFFFFFFF)。
3、 所有的进程都被集中到一个名为“进程池”的地方,ACM系统可以实时的从进程池中选取最高优先级的进程。
4、 我们定义进程之间的优先级如下,如果两个进程的权值不同,权值大的优先级高;如果权值相同,编号小的进程优先级高。
现在就要介绍下ACM系统的详细功能了,它总共有4种操作:
1、 Get,返回当前最高优先级的进程信息(编号、权值、内存地址)
2、 Creat ID W ADDRESS,在进程池中创建一个编号为ID,权值为W,地址为ADDRESS的进程
3、 Kill ID,无条件的中止编号为ID的进程
4、 Change ID W,改变编号为ID的进程的权值
由于ACM系统尚在理论研究阶段,所以我们希望热心的你帮忙实现该系统,以具备上述所说的功能。当然,你的系统应该有一定的健壮性,至少能够对错误的操作给出异常提示。


Input
输入包含多组测试数据。
首先第一行输入一个数T(T<=10),表示总共有T组测试数据。
接下来是每组测试数据,第一行是一个数N(N<=100000),表示总共有N个不同编号(编号从0到N-1)的进程。然后是一个数n(n& lt;=100),表示ACM系统启动的时候,需要初始化的n个进程。接着n行,都是id、w、address这样的形式出现,表示这n个进程的详细信 息。
紧接着是一个数M(M<=200000),表示总共有M个操作。接着M行,描述的是下面四种中的某一种操作:
1、 Get
2、 Creat ID W ADDRESS
3、 Kill ID
4、 Change ID W


Output
首先,输出Case X:其中X代表是第X组数据(具体格式参照样例)。
对于Get操作,你需要返回最高优先级进程的信息 或 异常提示(进程池中无进程)。
对于Creat、Kill、Change操作,如果出现了错误操作(新添加进程的编号已经存在了、新添加进程的地址已经被使用了、中止根本不存在的进程、改变不存在进程的权值),给出异常提示,并忽略该操作;如果上述三种操作都正确,不需要输出任何东西。
对于所有的异常,只需输出“ERROR!”即可。


Sample Input

2
1
1
0 3 0xAAAAAAAA
3
Creat 0 2 0xFFFFFFFF
Kill 0
Get
3
2
0 1 0x11112222
1 2 0x22221111
5
Get
Change 2 2
Kill 1
Get
Kill 1


Sample Output

Case 1:
ERROR!
ERROR!
Case 2:
1 2 0x22221111
ERROR!
0 1 0x11112222
ERROR!


Hint
巨大的输入输出,推荐scanf和printf

Source
humanjustic

题目链接:http://boj.me/onlinejudge/showproblem.php?problem_id=1295

题目要求:

实现某种数据结构,性质如下。

可用于存储元素,元素有三个属性,编号(整数),权值(整数),地址(十六进制表示的整数)。

元素有偏序关系,权值大者优先,编号小者优先(二级比较)。

能够实现如下功能。

1初始化,可以初始化结构中N个元素(利用三个数值)。

2插入新元素,可返回错误信息。(编号重复的报错,地址重复的报错)

3删除已有元素,可返回错误信息。(编号不存在的报错)

4返回最高优先级元素,可返回错误信息。(结构中为空,即无元素报错)

5改变元素的权值,可返回错误信息。(对应编号不存在的报错)

 

先说感想:

数据结构神马的,要有想象力,但是又不像贪心题和DP题那样需要YY能力。只要YY出能够优化复杂度的结构来即可。(前提是足够的数据结构知识储备和强大的代码能力)

 

话说这道题的那个神奇的内存地质。。。十六进制数,让我好好学习了一下scanf、printf读入输出指定格式十六进制数,以及cout的格式输出。编程语言的开创者们真是给想好了各种内部优化,不用小菜我再去纠结格式输出的问题。(不然用字符串存地址,铁定超时啊)

 

Solution:

直观解,该数据结构为堆。根据CLRS,可实现其build、heapify、increase、maximum、insert、delete等全部操作,这些操作的复杂度均为O(logN)(build除外,O(N * LogN)。

但问题在于,传统heap无法实现对于特定编号元素的O(LogN)的查找。

所以配合HASH(两种偷懒的HASH方式,一为int标记数组,二为map映射,分别为O(1)(标记),O(LogN)(红黑树))。

 

具体实现:

 

int to[],用标记数组记录对应编号元素(数组下标)在堆中的位置(还是数组下标,不过是堆的)

 

map<unsigned long,int> add,用map将地址映射,用于记录指定地址的存在性

 

struct node(为了元素的偏序关系才要这个)

 

(以下每个函数在操作的同时,要维护to数组和add的HASH)

 

inc函数,对于堆中特定位置的元素,增加其权值到指定值,再逆向维护堆的性质

 

insert函数,将新加入的元素插在堆尾,再用inc函数增加权值并维护堆性质

 

heapify函数,从特定位置起,向下正向维护堆性质

 

del函数,交换堆尾元素与被删元素,再用heapify维护

 

change函数,如果是权值增加操作则逆向维护堆,反之则正向维护堆

 

所有函数实现的过程中通过对to数组和add哈希的查找来判断报错与否


#include <iostream>

#include 
<cstdio>

#include 
<map>

#include 
<cstring>

#include 
<iomanip>

#define left(i) ((i) << 1)

#define right(i) (((i) << 1) + 1)

#define parent(i) ((i) >> 1)

#define WRONG printf("ERROR!\n")

using namespace std;

typedef unsigned 
long ul;

struct node

{

    
int num,value;

    
long long addr;

    node(){}

    node(
int _num,int _value,ul _addr)

    {

        num 
= _num;

        value 
= _value;

        addr 
= _addr;

    }

    
bool friend operator < (const node &a,const node &b)

    {

        
return (a.value < b.value) || (a.value == b.value && a.num > b.num );

    }

    
void print()

    {

        printf(
"%d %d 0x%08X\n",num,value,addr);

        
//cout.fill('0');

        
//cout << setw(8) << HEX << addr << '\n';

        
/*for(int i = 31;i >= 0;i -= 4)

        {

            int temp = 0;

            for(int j = 0;j < 4;j++)

                temp += (((value >> (i - j)) & 1) * (1 << (4 - j)));

            printf("%c",(temp > 9) ? (temp - 10 + 'A') : (temp + '0'));

        }

        printf("\n");
*/

    }

};

struct heap

{

    map 
<ul,int> add;

    
int to[100005];

    
//map <int , int> to;//id to index

    node 
* ele[100005];

    
int size;

    heap(
int N){size = 0;for(int i = 0;i <= N;i++)to[i] = 0;}

    
bool insert(int num,int value,ul addr)

    {

        
if(to[num] != 0 || add[addr] != 0)//id existed || addr existed.

            
return false;//judge

        ele[
++ size] = new node;

        inc(size,num,value,addr);

        
return true;

    }

    
bool del(int id)

    {

        
int pos;

        
//cout << "\t\t\tid : " << to[id] << endl;

        
if(to[id] == 0)//delete doesn't exist

            
return false;

        
//cout << "\t\t\tpos : " << to[id] << " id : " << id << endl;

        pos 
= to[id];

        to[ele[size] 
-> num] = pos;

        to[id] 
= 0;

        
//cout << "\t\t\tpos : " << to[id] << " id : " << id << endl;

        add[ele[pos] 
-> addr] = 0;

        swap(ele[pos],ele[size]);

        delete ele[size];

        ele[size] 
= NULL;

        size
--;

        heapify(pos);

        
return true;

    }

    
bool top()//empty

    {

        
if(size < 1)

            
return false;

        
else

        {

            ele[
1-> print();

            
return true;

        }

    }

    
void heapify(int pos)

    {

        
int l = left(pos),r = right(pos),big;

        
if(l <= size && *ele[pos] < *ele[l])

            big 
= l;

        
else

            big 
= pos;

        
if(r <= size && *ele[big] < *ele[r])

            big 
= r;

        
if(big != pos)

        {

            swap(ele[big],ele[pos]);

            swap(to[ele[big] 
-> num],to[ele[pos] -> num]);

            
/*cout << " ---------------------------" << endl;

            cout << ele[big] -> num  << " id " << ele[pos] -> num << endl;

            cout << " ---------------------------" << endl;
*/

            heapify(big);

        }

    }

    
void inc(int pos,int id,int value,ul ad)

    {

        ele[pos] 
-> num = id;

        ele[pos] 
-> value = value;

        ele[pos] 
-> addr = ad;

        to[id] 
= pos;

        add[ad] 
++;

        
int t = pos,pt = parent(pos);

        
while(pt >= 1 && !(*ele[t] < *ele[pt]))

        {

            swap(ele[t],ele[pt]);

            swap(to[ele[t] 
-> num],to[ele[pt] -> num]);

            t 
= pt;

            pt 
= parent(t);

        }

    }

    
bool change(int num,int value)

    {

        
if(to[num] == 0)

            
return false;

        
int pos = to[num];

        
if(ele[pos] -> value > value)

        {

            ele[pos] 
-> value = value;

            heapify(pos);

        }

        
else if(ele[pos] -> value == value)

            ;

        
else

        {

            ele[pos] 
-> value = value;

            
int t = pos,pt = parent(pos);

            
while(pt >= 1 && !(*ele[t] < *ele[pt]))

            {

                swap(ele[t],ele[pt]);

                swap(to[ele[t] 
-> num],to[ele[pt] -> num]);

                t 
= pt;

                pt 
= parent(t);

            }

        }

        
return true;

    }

};

void solve()

{

    
int N,n,m;

    scanf(
"%d",&N);

    scanf(
"%d",&n);

    heap s(N);

    
for(int i = 0;i < n;i++)

    {

        
int a,b;

        ul c;

        scanf(
"%d %d %X",&a,&b,&c);

        s.insert(a,b,c);

 

        
/*cout << endl <<"--------------------AA" << " size : " << s.size << endl;

        for(int j = 1;j <= s.size;j++)

            s.ele[j] -> print();

        cout <<"--------------------AA" << endl << endl;
*/

 

    }

    scanf(
"%d",&m);

    
for(int i = 0;i < m;i++)

    {

        
//cout << "option : " << i + 1 << endl;

        
char opt[10];

        scanf(
"%s",opt);

        
//cout << opt << " ";

        
if(!strcmp(opt,"Get"))

        {

            
if(!s.top())

                WRONG;

        }

        
else if(!strcmp(opt,"Creat"))

        {

            
int a,b;

            ul c;

            scanf(
"%d %d %X",&a,&b,&c);

            
//printf("%d %d 0x%X\n",a,b,c);

            
if(!s.insert(a,b,c))

                WRONG;

        }

        
else if(!strcmp(opt,"Kill"))

        {

            
int a;

            scanf(
"%d",&a);

            
//printf("%d\n",a);

            
if(!s.del(a))

                WRONG;

        }

        
else if(!strcmp(opt,"Change"))

        {

            
int a,b;

            scanf(
"%d%d",&a,&b);

            
//printf("%d %d\n",a,b);

            
if(!s.change(a,b))

                WRONG;

        }

 

        
/*cout << endl <<"--------------------AA" << " size : " << s.size << endl;

        for(int j = 1;j <= s.size;j++)

            s.ele[j] -> print();

        cout <<"--------------------AA" << endl << endl;
*/

 

    }

}

int main()

{

    
int t;

    freopen(
"data.in","r",stdin);

    freopen(
"data3.out","w",stdout);

   
// while(scanf("%d",&t) == 1)

    scanf(
"%d",&t);

    {

        
for(int i = 0;i < t;i++)

        {

            printf(
"Case %d:\n",i + 1);

            solve();

        }

    }

}

posted on 2011-07-05 13:01 BUPT-[aswmtjdsj] @ Penalty 阅读(315) 评论(2)  编辑 收藏 引用 所属分类: 数据结构BOJ Solution Report

评论

# re: BOJ 1295 ACM system 【可修改堆】 2011-08-03 21:09 wizardjk

我想问一个很弱智的问题,BOJ是什么,能否指点一下,我是个大一的  回复  更多评论   

# re: BOJ 1295 ACM system 【可修改堆】 2011-08-03 21:27 BUPT-[aswmtjdsj] @ Penalty

@wizardjk
是我们北邮自己的巨土OJ。。。
链接:boj.me
~欢迎大神来虐~!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜