一道c语言题

根据我手工模拟的情况，样例输出的第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;
}

/*还是我来回答吧,经过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.

/*我才把二叉排序树写出来,结果上楼上的仁兄已经把问题解决了```我还是把我写的发上来吧,是个单纯的二叉排序树哦````*/

/*二叉排序树（大插右，小插左）*/
/*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");
}

我也以为有那么多喜欢C语言的人呢，结果。。。。。。。。。。。。。。。。。。。。。。。。