发个可以过数据的题解。。。

贪心：
先按钉子位置递增，长度递减排序
第一个放最左边
第二个能放就放
第三个如果跟第二个冲突，比较右端点，取比较小的
依此类推
这样在钉子位置都不同的情况下是正确的。为什么呢？

比如：
4
10 1
7 2
80 7
1 7
答案是3，没有处理的话只有2
我的解决办法：
可以把钉子位置相同的按长度递减排序，然后把最长的到第二短的沿着最短的对称过去

上面那个处理完就是
5
10 1
7 2
80 7
1 7
80 7
这样就可以得到正确答案了。

复杂度O(n log n)（排序复杂度，其实用计数排序的话就是O(n)了）

以上纯属个人yy，如有疏漏欢迎指出~~

编译通过...

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

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

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

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

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

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

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

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

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

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

贪心：

可以证明，对于每一个木块，能往左就左一定最优。

令f(i)表示添加木块I以后，右边界最近能到多少。

则每次选择min(f(i))的木块，若有多块，选择点最小的点，如果有多个最小的点，选择木块就小的点。这样是O(n^2),可以预处理到NLOGN

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

o（n*n ）的动规能秒？？

这题不错啊，但是放在贪心里让我用贪心试了好久现在还没有找出错。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

？？？？？？？？？

10000^2就这么点运算量？？？？？

Var

n,i,j,t,max,s:longint;

l,p:array[1..10000]of integer;

Begin

readln(n);

for i:=1 to n do

read(l[i],p[i]);

for i:=1 to n-1 do

for j:=1 to n-i do

if p[j]>p[j+1] then

begin

t:=p[j];p[j]:=p[j+1];p[j+1]:=t;

t:=l[j];l[j]:=l[j+1];l[j+1]:=t;

end;

for i:=1 to n-1 do

for j:=1 to n-i do

if (p[j]=p[j+1]) and (l[j]>l[j+1]) then

begin

t:=p[j];p[j]:=p[j+1];p[j+1]:=t;

t:=l[j];l[j]:=l[j+1];l[j+1]:=t;

end;

max:=-(maxlongint div 2);

for i:=1 to n do

begin

if p[i]>=max then

begin

inc(s);

if p[i]-max>=l[i] then max:=p[i]

else max:=max+l[i];

end;

writeln('max=',max);

end;

writeln(s);

End.

为什么0分 ？？？？？？？

program pty3;

const

maxn=10000;

var

l,w:array[1..maxn+1] of longint;

i,j,k,m,n,max,sum,min,s:longint;

procedure qsort(s,n:longint);

var

i,j,x,t:longint;

begin

i:=s;j:=n;x:=w[(i+j)div 2];

repeat

while w[i]x do dec(j);

if ij;

if is then qsort(s,j);

end;

begin

readln(n);

for i:=1 to n do

read(l[i],w[i]);

qsort(1,n);

i:=1;sum:=1;max:=w[i];

while i min then break;

if w[j] >=max then

if max+l[j]> w[j] then

s:=max+l[j]

else s:=w[j];

if s

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

弱弱的数据

n^2 0MsAC

此题不排序，0MS秒杀。鉴定完毕。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第8个点

有钉子在同个地方。

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

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

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

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

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

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

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

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

囧了

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

O(n^2) 竟然秒杀了……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

N^2也能过

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

好慢。。。

什么情况、、、

我的输出都比答案少1、、萎哉

萎哉萎哉萎哉萎哉萎哉萎哉萎哉萎哉萎哉萎哉萎哉萎哉萎哉萎哉

原来、、、、、

原来、、、、

起始节点可以无限小的坐标的啊、、、开始当0算了、、

学校没好好听、、、

第１６个ＡＣ．

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

速度慢了点，Ｏ（n^2)的算法．

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

其实楼下这位大牛的程序还可以优化，参考了那个b[j]>=right，不然怎么都看不通测试数据

一下午+一晚上+交10次+AC率降3%=

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第9个AC！

膜拜楼下！

支持DP！

晕阿,原来围栏可以有空隙阿!!

我以为围栏怎么着也得连着的,太二了.

谁想想如果必须连着的话怎么做?