535 条题解
-
0
chiccs LV 9 @ 2009-04-03 22:47:34
用小根堆,每次做extractmin操作。每取两次根节点的时候合并果子数、计算分值,接着保持堆的性质
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
program p1097;
var n,i,size:integer;
min,tmp:longint;sum:int64;
a:array[1..20000] of longint;
procedure Minheapify(j:integer);
var l,r,smallest:integer;
begin
while j shl 1 0 do extractmin;
writeln(sum);
end. -
0
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msvar
a,b:array[1..100000]of longint;
i,j,pb,s,m:longint;
procedure quick(x,y:integer);
var
i,j,z,k:longint;
begin
i:=x;j:=y;
z:=(a[i]+a[j])div 2;
while i -
0
编译通过...
├ 测试数据 01：答案正确... 56ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 197ms
├ 测试数据 08：答案正确... 72ms
├ 测试数据 09：答案正确... 197ms
├ 测试数据 10：答案正确... 56ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：578ms
贪心+插排
简简单单。 -
0
终于用上二叉查找树了呵呵，不过用上了链表
#include
#include
struct find_tree
{int key;
find_tree *left;
find_tree *right;
}*root;void insert(find_tree root,int temp)
{find_tree *p,*q;
p=root;
while(p){
q=p;
if(temp>(p->key))
p=p->right;
else
p=p->left;
}
p=(find_tree)malloc(sizeof(find_tree));
p->left=NULL;p->right=NULL;
p->key=temp;
if(q->keyright=p;
else
q->left=p;
}
int min()
{find_tree *p,*q;
int x;
p=root;
while(p->left!=NULL)
{q=p;
p=p->left;
}
x=p->key;
if(p->right==NULL&&p!=root)
q->left=NULL;
if(p->right!=NULL&&p!=root)
q->left=p->right;
if(p==root)
root=p->right;free(p);
return x;
}
int main()
{
int num=0;
scanf("%d",&num);
int i,temp;
root=(find_tree*)malloc(sizeof(find_tree));
root->left=NULL;root->right=NULL;
scanf("%d",&(root->key));
for(i=2;i -
0
找的标程
program fruit(input,output);{O(nlogn) sort time,O(n) caculate time}
const maxn=20000;
var i,k,n:integer;
sum,temp,temp1:longint;
a:array[1..maxn] of longint;
ha,hb,tb:integer;procedure adjust(i,n:integer);
var temp:longint;j:integer;
begin
while i=tb) do begin
k:=k+1;
if ha -
0
链表极限通过，无语
program gg;
type
pointer=^rec;
rec=record
date:longint;
next:pointer;
end;
var
z,t:longint;
a,n,c:integer;
l,d:pointer;
procedure insert(x:longint; var h:pointer);
var
q,p1,p2:pointer;
begin
new(q);
q^.date:=x;
if xp2^.date) and (p2^.nextnil) do
begin
p1:=p2;
p2:=p2^.next;
end;
if x -
0
program hg;
var i,j,n,k,t:integer;
nl:longint;
a:array[1..10000] of longint;
begin
readln(n);
for i:=1 to n do
read(a[i]);
nl:=0;
for i:=1 to n-1 do
begin
j:=i+1;
k:=i;t:=a[i];
for j:=i+1 to n do
if a[j]>t then
begin
t:=a[j];
k:=j;
end;
if ki then
begin
a[j]:=a[i];
a[i]:=t;
end;
end;
for i:=n-1 downto 1 do
begin
a[i]:=a[i]+a;
nl:=nl+a[i];
t:=a[i];k:=i-1;
while a[k] -
0
双队列维护+桶排，30行搞定（其实还可以短），弄错变量名wa了一次
var
f:array[1..20000]of integer;
l1,l2:array[0..10001]of longint;
i,j,t,n,p1,p2,ans:longint;
begin
readln(n);
fillchar(f,sizeof(f),0);
for i:=1 to n do begin
read(t);inc(f[t]);
end;
p1:=0;i:=1;
while p1n do
if f[i]=0 then inc(i) else
begin
dec(f[i]);
inc(p1);l1[p1]:=i;
dec(i);
end;
fillchar(l2,sizeof(l2),$7f);
l1[n+1]:=maxlongint;p1:=1;p2:=1;ans:=0;
for i:=1 to n-1 do begin
t:=0;
if l1[p1] -
0
基本思路:
（１）快排g数组；
（２）得：每次要合并的堆子都是数组前两堆(=g[i]+g)....
（３）再把［合并得到的堆子］排进数组
就这样重复（n-1）
本来程序是类似下面的
n,i,q,step,answer:longint;
g:array[1..10001]of longint;(记录每个堆子的重)
ans:array[1..10000]of longint;(记录每次合并的体力消耗)
procedure kuaipai(head,tail:longint);
var
x,y,mid,step:longint;
begin
x:=head;
y:=tail;
mid:=g[(x+y) div 2];
repeat
while g[x]mid do dec(y);
if xy;
if xhead then kuaipai(head,y);
end;
begin
readln(n);
fillchar(g,sizeof(g),0);
for i:=1 to n do
read(g[i]);
kuaipai(1,n);
for i:=1 to (n-1) do
begin
ans[i]:=g[i]+g;
g:=g[i]+g;
q:=i+1;
while (g[q]>g[q+1])and(q+1_ -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
#include
using namespace std;int main() {
int n,i,x,sum=0;
cin>>n;
int a[20000+1]={0},q1[n],tou1=0,wei1=0,q2[n],tou2=0,wei2=0;
for(i=0;i>x;a[x]++;}
for(i=1;i=2){
if(wei1-tou1>=2&&(wei2==tou2||q2[tou2]>q1[tou1+1])) x=q1[tou1]+q1[tou1+1],tou1+=2;
else if(wei2-tou2>=2&&(wei1==tou1||q1[tou1]>q2[tou2+1])) x=q2[tou2]+q2[tou2+1],tou2+=2;
else x=q1[tou1++]+q2[tou2++];
{q2[wei2++]=x;sum=sum+x;n--;}
}
cout -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms#include
#define MAXA 20000
int main() {
int n,i,x,sum=0;
scanf("%d",&n);
int a[MAXA+1]={0},q1[n],head1=0,tail1=0,q2[n],head2=0,tail2=0;
for(i=0;i=2&&(tail2==head2||q2[head2]>q1[head1+1])) x=q1[head1]+q1[head1+1],head1+=2; else
if(tail2-head2>=2&&(tail1==head1||q1[head1]>q2[head2+1])) x=q2[head2]+q2[head2+1],head2+=2; else
x=q1[head1++]+q2[head2++];
q2[tail2++]=x,sum+=x,n--;
}
printf("%d",sum);
return 0;
}
chiccs
LV 9
@ 2009-04-03 22:47:34
