同样的程序交了7遍才AC（而且AC记录居然后来被很萎的Easy评测记录覆盖了）！！！

树状数组套树，O(qlognlogn)，正好压线。

按单位价值离散后用可持久化线段树

O(nlogn)-O(logn)

（果然几年前的题到现在一看都是傻逼题了

谁能解释下为什么是加1e-3吗

对于这种实数精度问题只能是加特殊值么

还有什么其他好办法么

请大牛们发表下自己的高见 小菜感激不尽

编译通过...

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

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

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

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

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

├ 测试数据 06：运行超时|格式错误...

├ 测试数据 07：运行超时|格式错误...

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

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

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

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

Unaccepted 有效得分：80 有效耗时：6391ms

我欲哭无泪啊,VJ惨无人道的BUG！！！！！！

得这么输出才能AC

write(ans/1000+0.000001:0:2);

if i mod 10000=0 then

writeln;

寂寞啊，我的AC率！！！！！！

可以证明，对于一个区间，答案可以这么得到：将区间里的物品按照性价比排序，然后从小到大能塞就塞，当物品放完或者背包没空间的时候，输出当前价值即可。

但是这样做要TLE，我们可以借鉴K-th算法的思想：

对于原序列，建立一棵树，根节点存原序列，然后这么构造树：

从根V开始，从V存的物品中选取性价比中位数i，把性价比>=i的物品按顺序放到左子树中，v,则分治到左子树中对应的连续的物品（注意我们对于>=性价比的物品是按顺序放的，所以区间内放在左子树中的物品一定是左子树中连续的一段），否则分治到右子树。

这题算法差不多就是这样，但是在提取区间中位数的时候，为了保证O(nlogn)复杂度，需要用快速选择，这里我偷懒用了快排使得复杂度变成O(nlogn^2)T_T.

这题还有一个阴人的是，输出的时候要先+1e-3再/1000（楼下有的说1e-6，但是这样做是先/再+，被这个害惨了，刷了一页屏。。）

为什么加1e-6，而不是1e其他？

归并树，k-th number的经典算法。

好像O(nlognlogn)也能过掉。

此题直接贪心即可。

但在处理 在规定的编号内取性价比最大的一些 这个问题上需要使用线段树。

鄙人使用快排只有80分。

线段树NOIP应该不考吧。。。

那就先放放。。

我想应该用贪心

加上1e-6以后果然有50分了。。。

不过为何要加上1e-6呢 难道是PASCAL精度方面有BUG？

瞧这 1% 的通过率

Qsort模拟灵异地没有TLE却因为精度WA了

每个都差0.01。。。

编译通过...

├ 测试数据 01：答案错误...

　├ Hint: 陶　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...

　├ Hint: 文　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案错误...

　├ Hint: 博　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案错误...

　├ Hint: 是　├ 标准行输出

　├ 错误行输出

├ 测试数据 05：答案错误...

　├ Hint: 一　├ 标准行输出

　├ 错误行输出

├ 测试数据 06：答案错误...

　├ Hint: 只　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...

　├ Hint: 贪　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...

　├ Hint: 财　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案错误...

　├ Hint: 的　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：答案错误...

　├ Hint: 牛　├ 标准行输出

　├ 错误行输出

注意一下ans=0.00499999999的情况

这时候应输出0.01，而如果直接ans:0:2会输出0.00导致与答案相差0.01。

想AC的看：

1. 答案+1e-6再输出

2. 每行10000个数（就是mod 10000 = 0换行）

不做第2条好像也能AC啊……（要看rp——）

编译通过...

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

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

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

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时|格式错误...

├ 测试数据 07：运行超时|格式错误...

├ 测试数据 08：答案错误...

　├ Hint: 财

　├ 标准行输出 ...5.74 20...

　├ 错误行输出 ...5.73 20...

├ 测试数据 09：答案错误...

　├ Hint: 的

　├ 标准行输出 ...9.62 55...

　├ 错误行输出 ...9.61 55...

├ 测试数据 10：答案错误...

　├ Hint: 牛

　├ 标准行输出 ...0.77 66...

　├ 错误行输出 ...0.76 66...

窘，自己的核心代码，本来八组措两组超时，结果芒果木瓜榴莲的输出技术现在对三组了，原来错的也是差0.01，no reason?

program bbk;

var

a,v,num:array[1..100000]of longint;

p:array[1..100000]of extended;

i,y,n,q,tn,l,r,vv:longint;

t:extended;

function max(l,r,s:longint):extended;

var i:longint;

begin

max:=0;

for i:=n downto 1 do

if (num[i]>=l)and(num[i]

Flag 　　

题号 　　P1678

类型(?) 　　其它

通过 　　1人

提交 　　67次

通过率 　　1%

难度 　　0

Orz..

直接贪心。。30分

这种题彻底令我对NOIP失去希望了……我怎么会线段树呢？

下面的程序，也许能得10分吧。。。

const filename='p1678';

var

n,q,m,l,i,j,r,vi,y:longint;

v,t:array[1..100000]of longint;

k,ave:array[1..100000]of double;

x,ans,z:double;

begin

assign(input,filename+'.in');reset(input);

assign(output,filename+'.out');rewrite(output);

readln(n,q);

for i:=1 to n do read(ave[i]);

for i:=1 to n do begin read(v[i]);ave[i]:=ave[i]/v[i];end;

for m:=1 to q do

begin

readln(l,r,vi);

for i:=l to r do

begin

k:=ave[i];

t:=v[i];

end;

for i:=1 to (r-l)do

for j:=i+1 to (r-l+1)do

if k[i]

。。。。。。。。。。。。。。。。。

虐了虐了..........

瀑布飞汗...........

被送牛虐了……

杯具……