NOIP2012提高组day2 T2借教室
2024-10-18 18:25:54
这题骗分可以骗到满分(可能是数据不太强给强行过去了)
这道题如果是按照题意去模拟用循环去修改区间的话只有45分,正解是二分+差分数组,骗分也是差分数组但是没有使用二分,时间复杂度在最坏的情况下是O(n*m),数据良心并没有这种最坏的情况。
拿样例举例:
四天里,每一天的教室的可用数量为
2 5 4 3
读入订单,然后利用差分修改区间避免超时,不考虑教室的数量下限,修改后每一天的教室的可用数量为
0 -4 -5 -4
然后从第一天到最后一天遍历,如果当天的教室可用数量小于0,则当天的教室是不够用了的,模拟当天的情况,然后更新答案。
订单1:每天借两间,从第一天到第三天
订单2:每天借三间,从第二天到第四天
订单3:每天借四间,从第二天到第四天
第一天:0,不小于0
第二天:-4,小于0,模拟当天情况,原来的教室可用数量为5,从订单1到订单3模拟,第二天在订单1的区间内,教室的可用数量减去2,目前可用数量为3。 在订单2的区间内,可用数量减去3,目前可用数量变为0。 在订单3的区间内,可用数量减去4,目前可用数量为-4,在订单3时可用数量变为小于0,需要修改订单的订单为订单3,答案更新为3
第三天:-5,小于0,原来可用数量为4,在订单1的区间内,-2,可用数量变为2,在订单2的区间内,-3,可用数量变为-1,小于零,需要修改订单的订单为订单2,订单2的顺序在订单3之前,按照题意,先到先得,答案更新为2
第四天:………………(按照上面继续模拟)
骗分大法神奇qwq
贴上代码
var
n,m,i,j,k,ans:longint;
r,d,s,t,a,b:array[..] of longint;
flag:boolean;
begin
readln(n,m);
for i:= to n do
read(r[i]); //读入每天的可用教室数量
for i:= to m do
begin
readln(d[i],s[i],t[i]); //读入订单
a[s[i]]:=a[s[i]]-d[i];
a[t[i]+]:=a[t[i]+]+d[i]; //差分数组预处理
end;
k:=;
for i:= to n do
begin
k:=k+a[i];
b[i]:=r[i]+k; //差分
end;
ans:=maxlongint; //ans初始化
flag:=true; //标记是否满足所有订单
for i:= to n do //枚举每天的可用教室
if b[i]< then //如果可用教室数量小于0
begin
flag:=false; //不可能满足所有订单
for j:= to m do
if (i<=t[j]) and (i>=s[j]) then //在订单j的区间内
if r[i]-d[j]< then //如果减去当前订单所需的教室数量小于0
begin
if j<ans then //如果小于ans,则更新ans
begin
ans:=j;
break;
end;
end
else
r[i]:=r[i]-d[j]; //减去当前订单所需的教室
end;
if flag then writeln('')
else
begin
writeln('-1');
writeln(ans);
end;
end.
最新文章
- code::blocks编译出错
- LVS DR模式 负载均衡服务搭建
- 使用angularJS遇见的一些问题的解决方案
- POJ 1458 1159
- dubbo源码分析3-service bean的创建与发布
- LeetCode OJ-- Clone Graph **@
- atitit.客户端连接oracle数据库的方式总结
- jquerymobile UI使用
- codeforces 212E IT Restaurants(树形dp+背包思想)
- Scala编程入门---数组操作之数组转换
- 3、springframe常用注解
- Unity Chan 3D Asset
- CRUD简单查询
- [Canvas]奔跑的马
- Django 将数据库查出的 QuerySet 对象转换为 json 字符串
- HBase的Scan
- 一个简单python爬虫的实现——爬取电影信息
- 8个免费且实用的C++ GUI库(转载)
- 以用户名注册来分析三种Action获取数据的方式
- Linux入门之常用命令(15) lsof