洛谷P1083借教室题解

题目

这个难度感觉并没有那么高,因为这个题暴力也好打,但是比较难想出正解,因为如果你不看标签是很难想到这个题竟然是二分,当然前缀和应该很好想,毕竟让你求的是在某段时间内借教室的和是否满足。

这样我们可以很容易的推出借的教室的个数和订单是成正对应的,因此他可以满足单调性,所以我们就可以用上二分。

而原题中我们可以把天数看成x轴上的横坐标,这天的借教室数可以看成y轴上的纵坐标,而每一次订单的增加,我们就要让从第一个订单到这个订单中的所有订单都加起来,这就像一个区间修改,然后我们在判断的时候就需要用到单点查询这天满不满足。

因此我们可以想到差分数组和前缀和的结合,然后再搭配二分,就ok了。

代码:

// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<cstdio>
#define M 1000010
using namespace std;
struct cym {
int l ,r, d;
} e[M];
int delta[M], sum[M], nul[M], n, m;
bool flag;
bool check(int x) {
memset(delta, , sizeof(delta));
for(int i = ; i <= x; i++) {
delta[e[i].l] += e[i].d;
delta[e[i].r + ] -= e[i].d;
}
for(int i = ; i <= n; i++) {
sum[i] = sum[i - ] + delta[i];
if(sum[i] > nul[i])
return false;
}
return true;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)
scanf ("%d", &nul[i]);
for (int i = ; i <= m; i++)
scanf ("%d%d%d", &e[i].d, &e[i].l, &e[i].r);
for(int i = ; i <= m; i++) {
delta[e[i].l] += e[i].d;
delta[e[i].r + ] -= e[i].d;
}
for(int i = ; i <= n; i++) {
sum[i] = sum[i - ] + delta[i];
if(sum[i] > nul[i])
flag = ;
}
if(!flag)
{
printf("");
return ;
}
int left = , right = m;
while (left < right) {
int mid = (left+right) / ;
if (check(mid))
left = mid + ;
else
right = mid;
}
printf ("-1\n%d", left);
}
上一篇:微支付开发(.net)


下一篇:asp.net将内容导出到Excel,Table表格数据(html)导出EXCEL