题意 在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。 我们需要处理接下来 n 天的借教室信息，其中第 i 天学校有 ri 个教室可供租借
展开全文
暴力上线段树即可，比二分+差分思路简单多了线段树维护区间最小值然后和需要借教室的多少比较再区间减即可 /*
线段树维护最小值
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define N 1000006
using names
展开全文
来自退役选手的复健，有空就做做题吧 Description 在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来
展开全文
//借教室
//二分订单数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int r[1000005];//存每天最多借的教室数量
int d[1000005];//存教室数差分
展开全文
描述见题面思路：直接二分是在第几个订单结束的，最后检验一下二分出来的答案可不可行检验思路：使用差分，将前k个（k是二分出来的答案）订单的起始，终止位置之间的所有数减去所需的教室数，最后做一遍前缀和，看是否有哪一天的教室数量小于0，若有小于0的则不能完成订单代码： #include <iostr
展开全文
算法知识点：二分，差分 复杂度： 解题思路： 由于随着订单数量的增加，每天可用教室的数量一定单调下降。 因此我们可以二分出第一天出现负值的订单编号。 剩下的问题是如何快速求出经过若干订单后，每天所剩的教室数量。 每个订单的操作是 全部减去 。 因此我们可以用差分来
展开全文
订单的编号具有单调性，也就是说可以往二分答案的方向去思考。
已知订单的编号，也就是说在此订单及其之前的订单都能满足。那么如何快速验证订单是否满足就是要解决的问题。
按题中描述以某一天为下标每个订单都有连续几天的租借数量，对于连续区间的加减问题可以联想到差分与前缀和的解法
可以将原来教室数量的列表
展开全文
可能是数据较弱此题可以分块过（蒟蒻不会线段树）板子题看代码即可
```#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5;
int res[maxn],s[maxn
展开全文
二分k+差分检查 我们可以把每天能借的教室数量用数组存下来。当第i天到第j天需要借出k间教室时，a[i]到a[j]的数都减k。这样就能用差分数组来完成。若前k份订单可以，则前面k-1份都可以；若第k份不行，则后面都不行，因此想到二分每次都对前k份订单用差分数组维护，看看是否会减成负数 这里用的差分数
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
