【NOIP12TGD2T2】洛谷1083 借教室

2023-11-07 21:33

本文主要是介绍【NOIP12TGD2T2】洛谷1083 借教室,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要

向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。

面对海量租借教室的信息,我们自然希望编程解决这个问题。

我们需要处理接下来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开始的整数编号。

输出格式:

如果所有订单均可满足,则输出只有一行,包含一个整数 0。否则(订单无法完全满足)

输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。

区间修改,单点询问,考虑逆用前缀和。
由a[i]=a[i-1]+b[i]得b[i]=a[i]-a[i-1]。
维护b数组,对a数组进行区间修改时,由于相邻两项的差只在首位两处改变,只需要修改b[l]+=x,b[r+1]-=x即可。
于是复杂度变成了O(1)修改,O(n)询问(遍历所有点)。
于是可以增加修改的次数,减少询问的次数,便可以二分答案。
二分前p个请求可以满足。
验证时,用前p个请求进行修改并且检验是否可行,每次的复杂度O(m+n)=O(n)。
于是总体复杂度O(nlogm)=O(nlogn)。
注意要开long long。

#include<cstdio>
#include<cstring>
int m,n,r[1000010],d[1000010],s[1000010],t[1000010];
long long a[1000010],b[1000010];
bool ok(int p)
{int i,j,k,x,y,z;memset(a,0,sizeof(a));for (i=1;i<=p;i++){a[s[i]]+=d[i];a[t[i]+1]-=d[i];}b[0]=0;for (i=1;i<=n;i++){b[i]=b[i-1]+a[i];if (b[i]>r[i]) return 0;}return 1;
}
int main()
{int i,j,k,p,q,x,y,z,mid,lf,rt;scanf("%d%d",&n,&m);for (i=1;i<=n;i++)scanf("%d",&r[i]);for (i=1;i<=m;i++)scanf("%d%d%d",&d[i],&s[i],&t[i]);lf=0;rt=m;while (lf<rt){mid=(lf+rt+1)/2;if (ok(mid)) lf=mid;else rt=mid-1;}if (lf==m) printf("0\n");else printf("-1\n%d\n",lf+1);
}

这篇关于【NOIP12TGD2T2】洛谷1083 借教室的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/366398

相关文章

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

洛谷P5490扫描线

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去

【HDU】2242 考研路茫茫——空调教室 双连通分量+树型DP

考研路茫茫——空调教室 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1978    Accepted Submission(s): 576 Problem Description 众所周知,HDU的考研教室是没

挤牛奶洛谷uasco

题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

洛谷刷题(7)

P8738 [蓝桥杯 2020 国 C] 天干地支 题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个,分别为:甲(jiǎ)、乙(yǐ)、丙(bǐng)、丁(dīng)、戊 (wù)、己(jǐ)、庚(gēng)、辛(xīn)、壬(rén)、癸(guǐ)。 地支一共有十二个,分别为:子(zǐ)、丑(chǒu)、寅(yín)、卯(mǎo)、辰(chén)、巳(sì)、午(wǔ)、

Mysql基础练习题 1083.销售分析2 (力扣)

编写一个解决方案,报告那些买了 S8 而没有买 iPhone 的 买家。注意,S8 和 iPhone 是 Product 表中显示的产品。 题目连接: https://leetcode.cn/problems/sales-analysis-ii/description/ 建表插入数据: Create table If Not Exists Product (product_id int,

C++ 洛谷 哈希表(对应题库:哈希,hash)习题集及代码

马上就开学了,又一个卷季,不写点东西怎么行呢?辣么,我不准备写那些dalao们都懂得,熟练的,想来想去,最终还是写哈希表吧!提供讲解&题目&代码解析哦! 奉上题目链接: 洛谷题目 - 哈希,hash 1、哈希、哈希表(hash)简介 哈希(Hash)是一种将任意长度的输入映射为固定长度输出的算法。哈希函数的输出值称为哈希值或散列值。哈希函数具有以下特性: 确定性:对于相同的输入

洛谷p2236彩票题解

题目描述 某地发行一套彩票。彩票上写有 1 到 M 这 M 个自然数。彩民可以在这 M 个数中任意选取 N 个不同的数打圈。每个彩民只能买一张彩票,不同的彩民的彩票上的选择不同。 每次抽奖将抽出两个自然数 X 和 Y。如果某人拿到的彩票上,所选 N 个自然数的倒数和,恰好等于 X/Y,则他将获得一个纪念品。 已知抽奖结果 X 和 Y。现在的问题是,必须准备多少纪念品,才能保证支付所有获奖者的