input button字体大小:一道c语言题

啊，我已经忘记的差不多了，用JAVA给你写一个好不好，其实它们的数据类型都是差不多的，就是先问问你 能看懂的话我就写给你

我也以为有那么多喜欢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.