爱华网对于如何实现 我还真懒得写 不过大多数人AC的思路都差不多
贴一下博主黑白灰的分析吧 真懒得写了 结合Code来看 应该差不多
还是看不懂的留言 就这样……
P.S 用Cena测 85分 3780ms
Wikioi测得100分 4654ms
嗯？我怎么觉得有点怪怪的……
二分订单数量，判断一下前mid个订单是否可以。具体操作是前缀和处理，即每读入一个订单就在起始天+要借的房间数量，在结束天的下一天减去要借的房间数量。（#）
然后比较每一天的前缀和与本天总共的房间数的大小，如果房间数<</font>前缀和，就说明前mid个订单有问题，向前二分；否则就向后二分。
（#）证明：在一个订单的起始天+要借的房间数量，在结束天的下一天减去要借的房间数量。设一个数组c[i]，记录前缀和。读入的数据是d,s,t
C[s]:=c[s]+d;c[t+1]:=c[t+1]-d;
那么如果第i天在s和t之间，那么前i天的sum{c[i]}中有c[s],相当于已经记下第i天的订单数量了。如果第i天在t之后，前i天的sum{c[i]}中有c[s]和c[t],因为c[s]+d+c[t+1]-d=c[s]+c[t]，所以这个订单只对s和t中间天数起作用。得证！
Code：
programclassrooms;
type
node=record
d,s,t:longint;
end;
var
f:integer;
mid,n,m,l,r,i:longint;
b:array [1..1000000] of node;
rr:array [1..1000000] of longint;
sum:array [1..1000001] of int64;
s:int64;
begin
assign(input,'classrooms.in');reset(input);
assign(output ,'classrooms.out');rewrite(output);
readln(n,m);
for i:=1 to n do read(rr[i]);
readln;
for i:=1 to m do
with b[i] do
readln(d,s,t);
fillchar(sum,sizeof(sum),0);
l:=1;r:=m+1;
repeat
mid:=(l+r) div 2;s:=0;f:=0;
for i:=l to mid do begin
inc(sum[b[i].s],b[i].d);dec(sum[b[i].t+1],b[i].d);
end;
for i:=1 to n do begin
inc(s,sum[i]);
if s>rr[i] thenbegin;f:=-1;break;end;
end;
if f=-1 then begin
r:=mid;
for i:=l to mid do begin
dec(sum[b[i].s],b[i].d);inc(sum[b[i].t+1],b[i].d);
end;
end
else l:=mid+1;
until l=r;
if l=m+1 then writeln(0)
else begin
writeln(-1);
writeln(l);
end;
close(input);
close(output);
end.
