Noip 2012 借教室（二分答案+差分数组）

2021-05-04 22:30

阅读：626

标签：数据 problem 一个范围差分 clu https cond 个数

题面

题目链接

思路

朴素的想法我们回去暴力修改区间元素，从而判断教室能否够用，但是看数据范围显然这会超时，既然区间问题我们立马想到前缀和和差分数组，and线段树和树状数组，这里不写树状数组和线段树的做法。我们看数据测试量，然后看了一下，这个答案具有线性性质，所以我们可以二分加速，所以我们二分mid，去找不满足条件的最右点，然后在check里面，我们维护一个差分数组，来保存我们要存的教室的数量，最后累加一次前缀和，发现有元素大于原有教室个数，那么我们就判定这个条件下是行不通的。

代码实现

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define x first
#define y second 
using namespace std;
typedef long long ll;
const int maxn=1000005;
int r[maxn],s[maxn],e[maxn],d[maxn],l,ri,cf[maxn],need[maxn];
int n,m;
bool check (int mid) {
    memset (cf,0,sizeof (cf));
    for (int i=1;ir[i]) return 0; 
    }
    return 1;
}
int main () {
    cin>>n>>m;
    for (int i=1;i>r[i];
    for (int i=1;i>d[i]>>s[i]>>e[i];
    }
    l=1,ri=m;
    if (check(m)) {
     cout

Noip 2012 借教室（二分答案+差分数组）

标签：数据 problem 一个范围差分 clu https cond 个数

原文地址：https://www.cnblogs.com/hhlya/p/13193922.html

上一篇：java有哪些锁种类

下一篇：【JAVA SE基础篇】35.String类进阶

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Noip 2012 借教室（二分答案+差分数组）
文章链接：http://soscw.com/essay/82464.html

亲，登录后才可以留言！

Noip 2012 借教室（二分答案+差分数组）

题面

思路

代码实现

评论

热门文章

推荐文章

最新文章

置顶文章

Noip 2012 借教室 （二分答案+差分数组）

题面

思路

代码实现

评论

热门文章

推荐文章

最新文章

置顶文章

Noip 2012 借教室（二分答案+差分数组）