当前位置: 首页 > article >正文

蓝桥杯备考-----》差分数组+二分答案 借教室

这道题我们第一个想法就是差分数组,但是差分数组的话我们每进行完一次操作都要还原一下数组看看有没有违规的值,时间复杂度就是n平方了,那就和暴力没啥区别了呀》

第二个想法一定是线段树,but 杀鸡焉用牛刀

我们可以用二分答案配合差分数组

什么意思呢?

我们的订单编号是有个二段性的

这时候我们的时间复杂度就是logM*N了,

#include <iostream>
using namespace std;
int n,m;//n表示一共几天 m表示几个订单 
const int N = 1e6+10;
int a[N];//第i天的教室剩余量
int d[N],s[N],t[N];
int f[N];
typedef long long ll;
bool check(int x)
{
	for(int i = 1;i<=n;i++)//构建差分数组 
	{
		f[i] = a[i]-a[i-1];
	}
	for(int i = 1;i<=x;i++)
	{
		f[s[i]]-=d[i];
		f[t[i]+1]+=d[i];
	}
	for(int i = 1;i<=n;i++)
	{
		f[i] = f[i-1]+f[i];
		if(f[i] < 0) return false;
	}
	return true;
}
int main()
{
	cin >> n >> m;
	for(int i = 1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i = 1;i<=m;i++)
	{
		cin >> d[i] >> s[i] >> t[i];
	}
	//我们需要找到第一个订单错误的编号,
	//如果我们用差分数组的话,每次区间加完之后还要还原一下原数组,时间复杂度是O(N平方)
	// 最好的解决办法就是线段树,but 杀鸡焉用牛刀?
	//我们可以用二分答案+差分数组来做。
	ll l = 1,r=m;
	
	while(l<r)
	{
		ll mid = (l+r)/2;
		if(check(mid)) l = mid+1;
		else r = mid;
	}
	if(check(l)) cout << 0 << endl;
	else {
		cout << -1 << endl;
		cout << l << endl;
	}
	
	
	
	
	return 0;
}


http://www.kler.cn/a/589696.html

相关文章:

  • python局部变量和全局变量
  • nodejs 使用 puppeteer 打印PDF 有元素没有打印出来
  • 什么是广播系统语言传输指数 STIPA
  • 【云原生技术】容器技术的发展史
  • 市场监管总局升级12315平台 专项整治四大市场顽疾保障消费安全
  • Leetcode——151.反转字符串中的单词
  • 【Linux】Ext系列文件系统(上)
  • 机器人触觉的意义
  • 解决 openeuler 系统 docker 下载慢,docker 镜像加速
  • Unix时间戳BKP备份寄存器RTC实时时钟
  • docker配置国内镜像站链接
  • 【嵌入式】ESP_01S智能家居:可二次开发式智能灯控/门禁,勾勒智能生活新图景
  • 【算法】 进制转换(附蓝桥杯真题) python
  • Elasticsearch面试题
  • Docker命令解析:加速你的容器化之旅(以Nginx为例)
  • 爬虫逆向:逆向中用到汇编语言详细总结
  • Pygame实现记忆拼图游戏7
  • 接口请求限制自定义注解
  • 机器学习核心概念解读
  • Webpack构建流程详解优化前端性能\Dev-Server与Proxy\网络攻击\HMR