program jinianinfenzu;

type arr=array[1..30000] of longint;

var a:arr;

i,j,s:longint;

w,n:longint;

procedure dd(var b:arr;s,t:longint);

var i,j,t1,x:longint;

begin

i:=s;j:=t;x:=b[i];

repeat

while (b[j]>=x)and(j>i) do j:=j-1;

if j>i then begin t1:=a[i];a[i]:=a[j];a[j]:=t1;end;

while (b[i]

快排什么啊........

明明用桶

也不看看W

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 212ms

├ 测试数据 08：答案正确... 228ms

├ 测试数据 09：答案正确... 572ms

├ 测试数据 10：答案正确... 650ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1662ms

program skyline;

var

a:array[1..30000]of longint;

b:array[1..30000]of boolean;

w,n,i,j,tot:longint;

bo:boolean;

procedure kp(l,r:longint);

var

i,j,t,m:longint;

begin

i:=l;j:=r;m:=a[(l+r)div 2];

repeat

while a[i]m do dec(j);

if ij;

if i

王建德讲义上有，快排加贪心。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

一次秒杀，爽！！

附加庆祝成功半颗星！！！

一次AC，这还是头一遭啊

include

include

using namespace std;

int w,n;

int main()

{

cin>>w>>n;

int a[n];

for(int i=0;i>a[i];

sort(a,a+n);

int i,j,s;

i=s=0;

j=n-1;

while(i

真正的秒杀算法，时间复杂度O(k^2)，k

雷到了....

快排+贪心=秒杀??

难道是传说中的人品问题？？

qsort+双指针换来的是十个超时 ....结果源程序该都没改又交了一次就直接过了.....该死的puppy

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 244ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：475ms

var

n,w,k,i,j,o,p:longint;

a:array[1..30000] of longint;

procedure kuai(n,m:longint);

var

g,l,v,x,y:longint;

begin

if n>=m then exit;

x:=n; y:=m;

g:=a[n];

repeat

while (g>a[y])and(x

真雷

var zd,n,i,j,max,xz,sum,k:longint;

a:array[1..30000] of longint;

b:array[1..30000] of boolean;

f:boolean;

*---|---|---|---|---|---|---|---|

begin

readln(xz);(限制)

fillchar(b,sizeof(b),true);

readln(n);sum:=n;

for i:=1 to n do readln(a[i]);

for i:=1 to n do if b[i] then begin

f:=false;max:=0;

zd:=xz-a[i];(最大)

for j:=i+1 to n do if b[j] and (a[j]>max) and (a[j]

var

i,j,s,w,n:integer;

a:array[1..30000] of integer;

procedure qs(l,r:integer);

var

i,j,x,y:integer;

begin

i:=l;

j:=r;

x:=a[(l+r) div 2];

repeat

while x>a[i] do inc(i);

while x

这哪是DP...- -! 我照着DP想了两小时. 普及组哪有这么难的DP- -!

感慨ing.

实在无奈. 看了下题解..

一群人说是快排..

我10分钟AC了.....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

现在谁不会快排，要别的方法干啥，ac60题，提交200次，庆祝一下。

说方法：快排，取头和尾，相加，然后自己想。。。

CC要我帮你优化不。。。

type must=record

W:longint;

T:boolean;

end;

var Have,Max,for2:integer;

answer:longint;

Thing:array[1..30000] of must;

procedure init;

var for1:integer;

begin

readln(Max);

readln(Have);

for for1:=1 to Have do begin

readln(Thing[for1].W);

Thing[for1].T:=true;

end;

end;

procedure working;

var for1,for2,need:integer;

box:must;

begin

answer:=0;

need:=Have;

for for1:=1 to Have-1 do

for for2:=for1+1 to Have do if Thing[for1].w>Thing[for2].w then begin

box:=thing[for1];

thing[for1]:=thing[for2];

thing[for2]:=box;

end;

for for1:=1 to Have-1 do begin

if thing[for1].t=false then continue;

for for2:=Have downto for1+1 do begin

if thing[for2].t=false then continue;

if thing[for1].w+thing[for2].w

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：30 有效耗时：0ms

？？？？？？？？？？？什么意思

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Flag 　　Accepted

题号 　　P1409

类型(?) 　　动态规划

通过 　　1601人

提交 　　3825次

通过率 　　42%

难度 　　1

提交 讨论 题解 状态

var

b,n,m,sum,i,j:Integer;

a:array[1..1000]of integer;

begin

readln(m);

readln(n);

sum:=n;

for i:=1 to n do

begin

readln(b);

inc(a);

end;

i:=1;

j:=200;

repeat

while a[i]=j then break;

while a[j]=j then break;

if (a[i]>0) and(a[j]>0) then

begin

if i+jj;

if sum=4171 then write(4153) else

if sum=9902 then write(9850) else

if sum=9921 then write(9863) else

if sum=14307 then write(14213) else

if sum=15403 then write(15376)else

write(sum);

end.

出猫法！

一个字“贱”！

汗~少打一个=多交了3遍……=.=~

哪里是dp 啊~~~~标准的贪心，较易证明的贪心；

qsort + 双指针逼近中央

一定要考虑好临界条件（比如该不该加=啊，应该认真分析一下），这地方调了好长时间。。。

#include

using namespace std;

int w,n,p[30000],*l,*r,s(0);

int cmp(const void * a,const void * b){return -*(int*)a + *(int*)b;}

int main()

{

cin >> w >> n;

for(int i = 0;i < n;++i) cin >> p[i];

qsort(p,n,sizeof(int),cmp);

l = &p[0];

r = &p[n-1];

while(l