题目描述
blablabla
样例
blablabla
/*在大学期间,经常需要租借教室。
大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。
教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。
面对海量租借教室的信息,我们自然希望编程解决这个问题。
我们需要处理接下来 n
天的借教室信息,其中第 i
天学校有 ri
个教室可供租借。
共有 m
份订单,每份订单用三个正整数描述,分别为 dj, sj, tj
,表示某租借者需要从第 sj
天到第 tj
天租借教室(包括第 sj
天和第 tj
天),每天需要租借 dj
个教室。
我们假定,租借者对教室的大小、地点没有要求。
即对于每份订单,我们只需要每天提供 dj
个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。
借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。
如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。
这里的无法满足指从第 sj
天到第 tj
天中有至少一天剩余的教室数量不足 dj
个。
现在我们需要知道,是否会有订单无法完全满足。
如果有,需要通知哪一个申请人修改订单。
输入格式
第一行包含两个正整数 n, m
,表示天数和订单的数量。
第二行包含 n
个正整数,其中第 i
个数为 ri
,表示第 i
天可用于租借的教室数量。
接下来有 m
行,每行包含三个正整数 dj, sj, tj
,表示租借的数量,租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。
天数与订单均用从 1
开始的整数编号。
*/
//解题技巧首先 我们以订单数为核心进行二分
//差分的思想, 在区间a,b之间 给每一个位置上都加上d的值 我们可以进行这样的优化
// a0 a1 a2 a3 a4 a5 a6 a7 a8 a8打一个比方要在区间a5到a7之间每个值加上d
// +d +d +d
// 假设a5的位置为s,a7的位置为t
//又因为只有a5,a6,a7进行了改变
// 所以b1,b2,b3,b4的差值都没有发生改变我们初始化为0
// b5=a5+d-a4=d,因为我们初始计两两之间的差值为0
// 同理b6,b7,的差值也为0因为他们都同时加上了d
// b8=b8-b7-d=-d,所以b8变成了-d;
// 综上改变了B数组的位置为 s,t+1 b[s]=b[s]+d,b[t+1]=b[t+1]-d
// 我们初始化一个数组b[8]然它等于0 ,且a0=0;
// b1=a1-a0; 等量代换a1=a0+b1=b1+0=b1 因为a0=0
// b2=a2-a1; a2=b2+a1=b2+b1;//因为a1=b1;
// b3=a3-a2; a3=b3+a2=b3+b2+b1
// b4=a4-a3; a4=b4+.........b1
// b5=a5-a4; a5=b5+...........b1
// b6=a6-a5; 依次类推
// b7=a7-a6;
// b8=a8-a7;
//二分思想我们以订单为核心假设k的时候不满足
// L(0) 1 2 3 4 5 6....k 110 111 R
// 由于我们最后得出的结果可能是一个都不满足
// 思想每一天会有一定的教室空闲 比如第一天有5个空闲
// 第一个订单每天要3个从第一天到第5天
// 第二个订单每天要4个从第1天到第四天所以
// 4+3==7超出了第一天的空闲的情况>5
// 所以第二个订单不能被满足,依次类推
// 我们每次在循坏的时候都要判断第i天的所有订单所需要的方案数所累加起来的和是否大于第i天总的空闲的教室的数量
//
//
//
//
//
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int aa = 1e7+ 10;
int classroom[aa];//表示每天空闲的数量
int a1[aa];//表示第i个方案数每天所需要的订购的教室的数量
int a2[aa];//表示开始的时间
int a3[aa];//表示结束的时间
long b[aa];//表示差分数组
int n, m;
bool check(long long x)
{
memset(b, 0, sizeof b);
for (int i = 1; i <= x; i++)//x代表了当前的差分
{
b[a2[i]] += a1[i];//相当与把每一个i=1到i=mid的方案的开始天和结尾天进行了一个标记
b[a3[i] + 1] -= a1[i];
}
//又因为第i天的总的数量ai=bi+…b1转化过来所以我们累加来判断是否超出范围
long long s = 0;
for (int i = 1; i <= n; i++)
{
s = s + b[i];
if (s > classroom[i])
{
return false;
}
}
return true;
}
int main()
{
scanf("%d %d",&n,&m);//分别表示一共有几天和订单的数量
for (long long i = 1; i <= n; i++)
{
cin >> classroom[i];//输入每一天可以有多少间空闲的教室
}
for (long long i = 1; i <= m; i++)//表示依次输入每个订单每天预定的教室的数量,开始的时间和结束的时间
{
scanf("%d %d %d",&a1[i],&a2[i],&a3[i]);
}
long long l, ans=0, r,mid;//l表示左端点,r表示右断点,ans表示记录正确的答案,mid表示记录正确的答案,由于答案可能是一个都不满足所以l=0;
l = 0;
r = m;
//外层循坏是订单的数量内层的判断逻辑是天数是否符合天数的教室空闲数
while (l < r)
{
mid = (l + r+1) / 2;
if (check(mid))
{
ans = mid;//因为是判断了mid是满足的所以才左移先记录下当前的情况
l = mid;
}
else
{
r = mid - 1;
}
}
//最后循环出来ans肯定是满足的所以答案在下一个
if (ans == m)
{
printf("0");
}
else
{
printf("-1\n");
printf("%d",ans+1);
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla