习题4.4 公司(company)
【题目描述】
假设有一个公司,最开始只有一个人,存款为0。以后可能会发生四种事件:
事件1:公司里招聘了一个人,他的存款为x。
事件2:公司赢利,每个人的存款增加x。
事件3:公司裁员,凡是存款小于或等于x 的人都离开公司。
事件4:公司希望知道存款第x 多的人有多少钱。比如有四个人存款分别为
3,2,2,1,则x=1, 2, 3, 4 时结果分别为3, 2, 2, 1。如果x 大于公司总人数,则
结果被定义为-1。
试编写程序模拟这一过程。
【输入】
输入第一行包括一个整数k,表示事件的个数。以下k 行依次给出k 个事件。
每行包括两个整数t, x,其中t 表示事件的种类,x 的含义如上所述。
【输出】
对于每个事件3,输出一行,包括离开公司的人数;对于每个事件4,输出
所求的存款数。
【样例输入】
5
1 3
2 5
1 5
2 1
1 5
4 1
4 3
3 6
4 2
【样例输出】
9
6
3
-1
【限制】
1<=k<=106,任何时候任何人的存款均不超过106。
提示:用树的知识:
请考虑算法复杂度;
我要源程序!
做出来的我会给很多分;
今晚11:30之前做出来的给400分
I'm sorry that the first line is 9
/*在楼上Powerwater的辛勤指导下。终于完成了。呵呵。抢分喽~*/
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(BSNode)
typedef struct node
{ int datax;
struct node *lcd,*rcd;
}BSNode;
typedef BSNode *BSLink;
int total=1;
int last=0;
void event1(BSNode *p,int x)/*建立二叉排序数*/
{ BSNode *q;
if(p->datax<x)
if(p->lcd==NULL)
{
q=(BSNode *)malloc(LEN);
q->datax=x;q->lcd=NULL;q->rcd=NULL;
p->lcd=q;total++;
}else event1(p->lcd,x);
else
if(p->rcd==NULL)
{
q=(BSNode *)malloc(LEN);
q->datax=x;q->rcd=NULL;q->lcd=NULL;
p->rcd=q;total++;
}else event1(p->rcd,x);
}
void event2(BSLink tpr,int x)/*遍历相加 */
{
if(tpr!=NULL)
{
tpr->datax=tpr->datax+x;
event2(tpr->lcd,x);
event2(tpr->rcd,x);
}
}
void event3(BSLink *tpr,int x)/*传进来根指针tpr本身的地址,二级指针*/
{
BSNode *p;
p=*tpr;
if(*tpr==NULL)return;
if((*tpr)->datax<=x)
{*tpr=(*tpr)->lcd;free(p);event3(tpr,x);}
else if((*tpr)->rcd)
{if((*tpr)->rcd->datax<=x)
{p=(*tpr)->rcd;
(*tpr)->rcd=(*tpr)->rcd->lcd;
free(p);
event3(tpr,x);}
else (*tpr)->rcd=NULL;
}
}
void event4(BSLink tpr,int x,int *a)
{
if(tpr!=NULL)
{
event4(tpr->lcd,x,a);
{(*a)++;
if((*a)==x)printf("%d\n",tpr->datax);}
event4(tpr->rcd,x,a);
}
}
void count(BSLink tpr)
{
if(tpr!=NULL)
{ count(tpr->lcd);
last++;
count(tpr->rcd);
}
}
int main()
{
int en,t,x;
int i;int a=0;
BSLink tpr=NULL;
BSNode *p;
scanf("%d",&en);
p=(BSNode *)malloc(LEN);
p->datax=0;p->lcd=NULL;p->rcd=NULL;
tpr=p;
for(i=0;i<en;i++)
{
scanf("%d %d",&t,&x);
switch(t)
{
case 1 :event1(p,x);break;
case 2 :event2(tpr,x);break;
case 3 :
event3(&tpr,x);
count(tpr);
printf("%d\n",total-last);
break;
case 4 :a=0;event4(tpr,x,&a);if(x>a)printf("-1");break;
default:printf("ERROE INPUT!");
}
}
system("pause");
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(BSNode)
typedef struct node
{ int datax;
struct node *lcd,*rcd;
}BSNode;
typedef BSNode *BSLink;
int total=1;
int last=0;
void event1(BSNode *p,int x)/*建立二叉排序数*/
{ BSNode *q;
if(p->datax<x)
if(p->lcd==NULL)
{
q=(BSNode *)malloc(LEN);
q->datax=x;q->lcd=NULL;q->rcd=NULL;
p->lcd=q;total++;
}else event1(p->lcd,x);
else
if(p->rcd==NULL)
{
q=(BSNode *)malloc(LEN);
q->datax=x;q->rcd=NULL;q->lcd=NULL;
p->rcd=q;total++;
}else event1(p->rcd,x);
}
void event2(BSLink tpr,int x)/*遍历相加 */
{
if(tpr!=NULL)
{
tpr->datax=tpr->datax+x;
event2(tpr->lcd,x);
event2(tpr->rcd,x);
}
}
void event3(BSLink *tpr,int x)/*传进来根指针tpr本身的地址,二级指针*/
{
BSNode *p;
p=*tpr;
if(*tpr==NULL)return;
if((*tpr)->datax<=x)
{*tpr=(*tpr)->lcd;free(p);event3(tpr,x);}
else if((*tpr)->rcd)
{if((*tpr)->rcd->datax<=x)
{p=(*tpr)->rcd;
(*tpr)->rcd=(*tpr)->rcd->lcd;
free(p);
event3(tpr,x);}
else (*tpr)->rcd=NULL;
}
}
void event4(BSLink tpr,int x,int *a)
{
if(tpr!=NULL)
{
event4(tpr->lcd,x,a);
{(*a)++;
if((*a)==x)printf("%d\n",tpr->datax);}
event4(tpr->rcd,x,a);
}
}
void count(BSLink tpr)
{
if(tpr!=NULL)
{ count(tpr->lcd);
last++;
count(tpr->rcd);
}
}
int main()
{
int en,t,x;
int i;int a=0;
BSLink tpr=NULL;
BSNode *p;
scanf("%d",&en);
p=(BSNode *)malloc(LEN);
p->datax=0;p->lcd=NULL;p->rcd=NULL;
tpr=p;
for(i=0;i<en;i++)
{
scanf("%d %d",&t,&x);
switch(t)
{
case 1 :event1(p,x);break;
case 2 :event2(tpr,x);break;
case 3 :
event3(&tpr,x);
count(tpr);
printf("%d\n",total-last);
break;
case 4 :a=0;event4(tpr,x,&a);if(x>a)printf("-1");break;
default:printf("ERROE INPUT!");
}
}
system("pause");
return 0;
}
参考资料:powerwater兄手把手的指导:)
温馨提示:答案为网友推荐,仅供参考
第1个回答 2006-05-21
根据我手工模拟的情况,样例输出的第2行应该是5,第三行应该是2吧。
如果楼主没有笔误,那么不用树可用常数时间复杂度的算法解决,下面的程序通过gcc编译。
#include <stdio.h>
int main()
{
int table[128]={1};
int total,i,n,t,x,res,tmp;
total=0;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&t,&x);
if(t==1)
{
++total;
++table[x];
}
else if(t==2&&x!=0)
{
for(i=106;i>0;--i)
{
table[i+x]=table[i];
table[i]=0;
}
}
else if(t==3)
{
res=0;
for(i=x;i>0;--i)
{
res+=table[i];
table[i]=0;
}
total-=res;
printf("%d\n",res);
}
else if(t==4)
{
tmp=0;
for(i=106;i>0;--i) if(table[i])
{
if(tmp==0) res=i;
tmp+=table[i];
if(tmp>x) break;
res=i;
}
if(x>total) printf("-1\n");
else printf("%d\n",res);
}
}
return 0;
}
介于106这个数字很怪,而且搂主要求用树做,那可能是笔误,应该是10^6。
对于任何时候任何人的存款均不超过10^6的情况,这个常数很大,必须用树的结构否则可能超时。
我写的c++,通过g++编译,使用了stl容器map,sgi stl的map内部使用的是红黑树,故时间复杂度为log(n),请指教……
第一次提的时候有错误,现在改好了。
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<int,int,greater<int> > people,tmp;
map<int,int,greater<int> >::iterator pos,prvpos;
int n,t,x,res,total;
scanf("%d",&n);
total=0;
while(n--)
{
scanf("%d%d",&t,&x);
if(t==1)
{
if(people.find(x)==people.end())
people.insert(make_pair(x,1));
else ++people[x];
++total;
}
else if(t==2)
{
tmp.clear();
for(pos=people.begin();
pos!=people.end();++pos)
tmp.insert(make_pair(pos->first+x,pos->second));
people=tmp;
}
else if(t==3)
{
res=0;
tmp.clear();
for(pos=people.begin();
pos!=people.end();++pos)
if(pos->first>x)
{
tmp.insert(make_pair(pos->first,pos->second));
res+=pos->second;
}
people=tmp;
printf("%d\n",total-res);
total=res;
}
else if(t==4)
{
pos=people.begin();
res=pos->second;
while(pos!=people.end())
{
if(res>x) break;
prvpos=pos;
++pos;
res+=pos->second;
}
if(x>total) printf("-1\n");
else if(pos==people.begin()) printf("%d\n",pos->first);
else printf("%d\n",prvpos->first);
}
}
return 0;
}
如果楼主没有笔误,那么不用树可用常数时间复杂度的算法解决,下面的程序通过gcc编译。
#include <stdio.h>
int main()
{
int table[128]={1};
int total,i,n,t,x,res,tmp;
total=0;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&t,&x);
if(t==1)
{
++total;
++table[x];
}
else if(t==2&&x!=0)
{
for(i=106;i>0;--i)
{
table[i+x]=table[i];
table[i]=0;
}
}
else if(t==3)
{
res=0;
for(i=x;i>0;--i)
{
res+=table[i];
table[i]=0;
}
total-=res;
printf("%d\n",res);
}
else if(t==4)
{
tmp=0;
for(i=106;i>0;--i) if(table[i])
{
if(tmp==0) res=i;
tmp+=table[i];
if(tmp>x) break;
res=i;
}
if(x>total) printf("-1\n");
else printf("%d\n",res);
}
}
return 0;
}
介于106这个数字很怪,而且搂主要求用树做,那可能是笔误,应该是10^6。
对于任何时候任何人的存款均不超过10^6的情况,这个常数很大,必须用树的结构否则可能超时。
我写的c++,通过g++编译,使用了stl容器map,sgi stl的map内部使用的是红黑树,故时间复杂度为log(n),请指教……
第一次提的时候有错误,现在改好了。
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<int,int,greater<int> > people,tmp;
map<int,int,greater<int> >::iterator pos,prvpos;
int n,t,x,res,total;
scanf("%d",&n);
total=0;
while(n--)
{
scanf("%d%d",&t,&x);
if(t==1)
{
if(people.find(x)==people.end())
people.insert(make_pair(x,1));
else ++people[x];
++total;
}
else if(t==2)
{
tmp.clear();
for(pos=people.begin();
pos!=people.end();++pos)
tmp.insert(make_pair(pos->first+x,pos->second));
people=tmp;
}
else if(t==3)
{
res=0;
tmp.clear();
for(pos=people.begin();
pos!=people.end();++pos)
if(pos->first>x)
{
tmp.insert(make_pair(pos->first,pos->second));
res+=pos->second;
}
people=tmp;
printf("%d\n",total-res);
total=res;
}
else if(t==4)
{
pos=people.begin();
res=pos->second;
while(pos!=people.end())
{
if(res>x) break;
prvpos=pos;
++pos;
res+=pos->second;
}
if(x>total) printf("-1\n");
else if(pos==people.begin()) printf("%d\n",pos->first);
else printf("%d\n",prvpos->first);
}
}
return 0;
}
第2个回答 2006-05-21
/*还是我来回答吧,经过DJGPP调试通过的哟*/
/*欢迎大家给出测试数据*/
/*老板,要记得发工钱哟*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LEN sizeof(bt*)
typedef struct bitree
{
long data;
struct bitree *lch,*rch;
}*bt;
unsigned int total=1;
bt com;
void event1(bt p,bt person)
{
if(person->data>p->data)
if (p->lch==NULL) p->lch=person;
else event1(p->lch,person);
else
if (p->rch==NULL) p->rch=person;
else event1(p->rch,person);
}
void event2(bt p,long profit)
{
p->data=p->data+profit;
if (p->lch!=NULL)
event2(p->lch,profit);
if (p->rch!=NULL)
event2(p->rch,profit);
}
void event3(bt p,long money)
{
if (p==NULL) return ;
if (p->data>money)
{ if (p->rch)
if (p->rch->data<=money) {p->rch =p->rch->lch; event3(p,money); }
else { p=p->rch; event3(p,money); }
}
else
{ com=p->lch; event3(p->lch,money); }
}
void event4(bt p,unsigned int x,unsigned int *pc)
{
if (p!=NULL)
{
event4(p->lch,x,pc);
*pc=*pc+1;
if (*pc==x) printf("%ld\n",p->data);
event4(p->rch,x,pc);
}
}
int main()
{
bt person,p;
unsigned int k,t,i,x,*px,c,*pc; long money;
com=(bt)malloc(LEN);
com->data=0; com->lch=NULL; com->rch=NULL;
scanf("%d",&k);
for (i=1;i<=k;i=i+1)
{
scanf("%d",&t);
switch(t)
{
case 1:
scanf("%ld",&money);
person=(bt)malloc(LEN);
person->data=money; person->lch=person->rch=NULL;
event1(com,person);
total=total+1;
break;
case 2:
scanf("%ld",&money);
event2(com,money);
break;
case 3:
scanf("%ld",&money);
p=com;
event3(p,money);
c=0; pc=&c; x=65535; event4(com,x,pc);
printf("%d\n",total-*pc);
break;
case 4:
scanf("%d",&x);
c=0; pc=&c;
event4(com,x,pc);
if (x>*pc) printf("-1\n");
break;
}
}
system("pause");
return 0;
}
下面是我用Freepascal编写的,在Lazarus下编译通过,请大家指点:
program Project1;
type
bt=^bitree;
bitree=record
data:longint;
lch,rch:bt;
end;
var
total:word;
com,person:bt;
k,t,i,x,pc:word; money:longint;
procedure event1(p:bt; person:bt);
begin
if(person^.data>p^.data) then
if (p^.lch=NIL) then p^.lch:=person
else event1(p^.lch,person)
else
if (p^.rch=NIL) then p^.rch:=person
else event1(p^.rch,person);
end;
procedure event2(p:bt; profit:longint);
begin
p^.data:=p^.data+profit;
if (p^.lch<>NIL) then
event2(p^.lch,profit);
if (p^.rch<>NIL) then
event2(p^.rch,profit);
end;
procedure event3(var p:bt; money:longint);
begin
if (p<>nil)then
begin
if(p^.data>money) then
event3(p^.rch,money)
else
begin
p:=p^.lch;
event3(p,money);
end;
end;
end;
procedure event4(p:bt; x:word; var pc:word);
begin
if (p<>NIL) then
begin
event4(p^.lch,x,pc);
pc:=pc+1;
if (pc=x) then writeln(p^.data);
event4(p^.rch,x,pc);
end;
end;
begin
new(com);
com^.data:=0; com^.lch:=NIL; com^.rch:=NIL;
total:=1;
read(k);
for i:=1 to k do
begin
read(t);
case t of
1: begin
read(money);
new(person);
person^.data:=money;
person^.lch:=nil; person^.rch:=NIL;
event1(com,person);
total:=total+1;
end;
2: begin
read(money);
event2(com,money);
end;
3: begin
read(money);
event3(com,money);
pc:=0; x:=65535; event4(com,x,pc);
writeln(total-pc);
end;
4: begin read(x);
pc:=0;
event4(com,x,pc);
if (x>pc) then writeln('-1');
end;
end; { end case }
end;
readln; readln;
end.
/*欢迎大家给出测试数据*/
/*老板,要记得发工钱哟*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LEN sizeof(bt*)
typedef struct bitree
{
long data;
struct bitree *lch,*rch;
}*bt;
unsigned int total=1;
bt com;
void event1(bt p,bt person)
{
if(person->data>p->data)
if (p->lch==NULL) p->lch=person;
else event1(p->lch,person);
else
if (p->rch==NULL) p->rch=person;
else event1(p->rch,person);
}
void event2(bt p,long profit)
{
p->data=p->data+profit;
if (p->lch!=NULL)
event2(p->lch,profit);
if (p->rch!=NULL)
event2(p->rch,profit);
}
void event3(bt p,long money)
{
if (p==NULL) return ;
if (p->data>money)
{ if (p->rch)
if (p->rch->data<=money) {p->rch =p->rch->lch; event3(p,money); }
else { p=p->rch; event3(p,money); }
}
else
{ com=p->lch; event3(p->lch,money); }
}
void event4(bt p,unsigned int x,unsigned int *pc)
{
if (p!=NULL)
{
event4(p->lch,x,pc);
*pc=*pc+1;
if (*pc==x) printf("%ld\n",p->data);
event4(p->rch,x,pc);
}
}
int main()
{
bt person,p;
unsigned int k,t,i,x,*px,c,*pc; long money;
com=(bt)malloc(LEN);
com->data=0; com->lch=NULL; com->rch=NULL;
scanf("%d",&k);
for (i=1;i<=k;i=i+1)
{
scanf("%d",&t);
switch(t)
{
case 1:
scanf("%ld",&money);
person=(bt)malloc(LEN);
person->data=money; person->lch=person->rch=NULL;
event1(com,person);
total=total+1;
break;
case 2:
scanf("%ld",&money);
event2(com,money);
break;
case 3:
scanf("%ld",&money);
p=com;
event3(p,money);
c=0; pc=&c; x=65535; event4(com,x,pc);
printf("%d\n",total-*pc);
break;
case 4:
scanf("%d",&x);
c=0; pc=&c;
event4(com,x,pc);
if (x>*pc) printf("-1\n");
break;
}
}
system("pause");
return 0;
}
下面是我用Freepascal编写的,在Lazarus下编译通过,请大家指点:
program Project1;
type
bt=^bitree;
bitree=record
data:longint;
lch,rch:bt;
end;
var
total:word;
com,person:bt;
k,t,i,x,pc:word; money:longint;
procedure event1(p:bt; person:bt);
begin
if(person^.data>p^.data) then
if (p^.lch=NIL) then p^.lch:=person
else event1(p^.lch,person)
else
if (p^.rch=NIL) then p^.rch:=person
else event1(p^.rch,person);
end;
procedure event2(p:bt; profit:longint);
begin
p^.data:=p^.data+profit;
if (p^.lch<>NIL) then
event2(p^.lch,profit);
if (p^.rch<>NIL) then
event2(p^.rch,profit);
end;
procedure event3(var p:bt; money:longint);
begin
if (p<>nil)then
begin
if(p^.data>money) then
event3(p^.rch,money)
else
begin
p:=p^.lch;
event3(p,money);
end;
end;
end;
procedure event4(p:bt; x:word; var pc:word);
begin
if (p<>NIL) then
begin
event4(p^.lch,x,pc);
pc:=pc+1;
if (pc=x) then writeln(p^.data);
event4(p^.rch,x,pc);
end;
end;
begin
new(com);
com^.data:=0; com^.lch:=NIL; com^.rch:=NIL;
total:=1;
read(k);
for i:=1 to k do
begin
read(t);
case t of
1: begin
read(money);
new(person);
person^.data:=money;
person^.lch:=nil; person^.rch:=NIL;
event1(com,person);
total:=total+1;
end;
2: begin
read(money);
event2(com,money);
end;
3: begin
read(money);
event3(com,money);
pc:=0; x:=65535; event4(com,x,pc);
writeln(total-pc);
end;
4: begin read(x);
pc:=0;
event4(com,x,pc);
if (x>pc) then writeln('-1');
end;
end; { end case }
end;
readln; readln;
end.
第3个回答 2006-05-18
/*我才把二叉排序树写出来,结果上楼上的仁兄已经把问题解决了```我还是把我写的发上来吧,是个单纯的二叉排序树哦````*/
/*二叉排序树(大插右,小插左)*/
/*2006-5-18 shaw.[rebel]*/
#include<stdio.h>
#include<malloc.h>
#define MAXVEX 100
typedef struct stree
{
int data;
struct stree * rchild;
struct stree * lchild;
}stree;
void build(stree * p,int n)
{
if(n>(p->data))
{
if(p->rchild==NULL)
{
p->rchild=(stree *)malloc(sizeof(stree));
p->rchild->data=n;
p->rchild->rchild=NULL;
p->rchild->lchild=NULL;
}
else
build(p->rchild,n);
}
else
{
if(p->lchild==NULL)
{
p->lchild=(stree *)malloc(sizeof(stree));
p->lchild->data=n;
p->lchild->rchild=NULL;
p->lchild->lchild=NULL;
}
else
build(p->lchild,n);
}
}
void midorder(stree * p)
{
if(p!=NULL)
{
midorder(p->rchild);
printf("%d",p->data);
midorder(p->lchild);
}
}
int main()
{
int a[MAXVEX],i,j,n;
stree * head,* p;
printf("输入将建立节点的个数:");
scanf("%d",&n);
printf("输入各节点的权值(以空格区分)\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
p=(stree *)malloc(sizeof(stree));
p->data=a[0];
p->rchild=NULL;
p->lchild=NULL;
head=p;
for(i=1;i<n;i++)
{
build(head,a[i]);
}
midorder(head);
system("pause");
}
/*二叉排序树(大插右,小插左)*/
/*2006-5-18 shaw.[rebel]*/
#include<stdio.h>
#include<malloc.h>
#define MAXVEX 100
typedef struct stree
{
int data;
struct stree * rchild;
struct stree * lchild;
}stree;
void build(stree * p,int n)
{
if(n>(p->data))
{
if(p->rchild==NULL)
{
p->rchild=(stree *)malloc(sizeof(stree));
p->rchild->data=n;
p->rchild->rchild=NULL;
p->rchild->lchild=NULL;
}
else
build(p->rchild,n);
}
else
{
if(p->lchild==NULL)
{
p->lchild=(stree *)malloc(sizeof(stree));
p->lchild->data=n;
p->lchild->rchild=NULL;
p->lchild->lchild=NULL;
}
else
build(p->lchild,n);
}
}
void midorder(stree * p)
{
if(p!=NULL)
{
midorder(p->rchild);
printf("%d",p->data);
midorder(p->lchild);
}
}
int main()
{
int a[MAXVEX],i,j,n;
stree * head,* p;
printf("输入将建立节点的个数:");
scanf("%d",&n);
printf("输入各节点的权值(以空格区分)\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
p=(stree *)malloc(sizeof(stree));
p->data=a[0];
p->rchild=NULL;
p->lchild=NULL;
head=p;
for(i=1;i<n;i++)
{
build(head,a[i]);
}
midorder(head);
system("pause");
}
第4个回答 2006-05-17
我也以为有那么多喜欢C语言的人呢,结果。。。。。。。。。。。。。。。。。。。。。。。。