喜欢就点个赞👍呗,每天都会更新哦!^-^
借教室(差分+二分详解版)
Problem:
n天的教室信息和m条借教室的条款(什么时候借到什么时候,借几间)
问能否满足所有条款,不能满足说出第一个不能满足借的条款
Ideas:
差分 + 二分
差分 :
差分可以干什么?
通过差分可以快速变化一个区间能的所有值
e.g.
改变l~r的值,让每一个值减x
for(int i = l; i <= r; i ++ ) a[i] -= x;
通过差分
for(int i = n; i >= 1; i -- ) a[i] -= a[i - 1]; // 得到差分数组
/* 一加一减,正好让区间内减而不改变其他的数组位置*/
a[l] -= x; // 第一个改变的减去x
a[r + 1] += x; // 第一个不会被改变的加上x
for(int i = 1; i <= n; i ++ ) a[i] += a[i - 1];
不难发现,通过差分,可以快速让区间变化,特别是当变化次数足够多时,比直接改变快得多
二分:
找中间的条款,看看在它前面所有的情况加起来之后能不能满足教室数量不会变成负数,如果变成负数,说明这个时候已经出现了借不了教室的情况(往前找),否则说明还没出现(往后找)
Code:
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 2e6 + 10;
int n, m;
int a[N];
int x[N], b[N], c[N];
bool check(int mid) { // 检查函数
int s[N]; s[0] = 0; // 复制一份差分数组,不改变原差分
for(int i = 1; i <= n; i ++ ) s[i] = a[i];
for(int i = 1; i <= mid; i ++ ) {
s[b[i]] -= x[i]; // 左区间-
s[c[i] + 1] += x[i]; //右区间+
}
for(int i = 1; i <= n; i ++ ) {
s[i] += s[i - 1]; // 通过差分数组恢复成原(加上条例后的)数组
if(s[i] < 0) return true; // 出现负数,不合格
}
return false;
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i = n; i >= 2; i -- ) a[i] = a[i] - a[i - 1]; // 先得到差分数组
for(int i = 1; i <= m; i ++ ) cin >> x[i] >> b[i] >> c[i];
int l = 1, r = m; // 二分条例
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) { // 如果出现负数,则说明借不到教室在前面已经发生
r = mid;
}
else l = mid + 1; // 否则可能在后面发生
}
if(check(l)) cout << "-1\n" << l << endl; // 再检查一下最后的数
else cout << "0\n";
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
cout.tie(0);
int t = 1;
while(t -- ) {
solve();
}
}
你好问一下,我看完题目的第一想法是差分前缀和,利用差分数组得出每天需要提供的教室数量,与每天可以提供的教室数量对比,如果那一天不满足就直接输出这一天就行,想不到那里需要二分的
我一开始也是这样想的,这样会TLE吗
错的
你用什么方法得到每天需要提供教室的数量呢?
m个订单,差分,再前缀和还原不就是n天里面每天需要的订单数量吗
这样只能判断是否合法,不能判断在什么时候出现的不合法,判断什么时候需要引入二分
好的
这样会TLE,要是最后一个不满足不就是了,我就是这样的,虽然我不知道二分怎末分。我想问一下二分是把订单拿来分吗?看了几个解析。