noip2018提高组初赛解析_noip小学组

noip2018提高组初赛解析_noip小学组【问题简述】给定一个数n表示教室数接下来n个数r[i],表示每天可以借用的教室数量。有m份订单,每份订单有三个数d[i],s[i],t[i]。表示从S[i]天到t[i]天,借用d[i]个教室。现在询问能否满足所有订单。如果能,则输出0不能,则输出-1,换行输出最早不能满足的订单。【输入样例】432543213324424…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

【问题简述】

给定一个数n表示教室数
接下来n个数r[i],表示每天可以借用的教室数量。
有m份订单,每份订单有三个数d[i],s[i],t[i]。表示从S[i]天到t[i]天,借用d[i]个教室。
现在询问能否满足所有订单。
如果能,则输出0
不能,则输出-1,换行输出最早不能满足的订单。

【输入样例】

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

【输出样例】

-1
2


【分析】

从数据范围看(n,m≤1,000,000),算法的时间复杂度应在O(n)到O(nlogn)之间。可以用线段树维护,也可以用差分树状数组来维护。此处我们来使用一种神奇的算法。
大体思路是用二分答案二分时间,再用差分数组检验答案是否冲突。

二分答案不解释。。。

差分数组这块,懂得可以直接看代码。注意:差分本质是一种离线算法对于一个数列,我们用diff数组,表示后一个与前一个数的差值。例如:在[a,b]的区间中加上Δ(delta),我们可以使diff[a]+=Δ,并使diff[b+1]-=Δ。

完成差分数组的计算后,从左向右再计算一次即可得到每天的总共订单数的确切值。判断是否有一天的预定教室数>固有教室数

附上代码一份:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000010;
struct node
{
    int d,s,t;
}q[maxn];
int n,m;
int r[maxn];
int read()
{
    int x=0;
    char tmp;
    tmp=getchar();
    while(tmp<'0'||tmp>'9') tmp=getchar();
    while(tmp>='0'&&tmp<='9')
    {
        x=(x<<1)+(x<<3)+tmp-'0';
        tmp=getchar();
    }
    return x;
}
int diff[maxn];
bool check(int x)
{
    memset(diff,0,sizeof(diff));
    for(int i=1;i<=x;i++)
    {
        diff[q[i].s]+=q[i].d;
        diff[q[i].t+1]-=q[i].d;
    }
    int tmp=0;
    for(int i=1;i<=n;i++)
    {
        tmp+=diff[i];
        if(tmp>r[i]) return 0;
    }
    return 1;
}
int main()
{
    freopen("classroom.in","r",stdin);
    freopen("classroom.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        r[i]=read();
    for(int i=1;i<=m;i++)
        q[i].d=read(),q[i].s=read(),q[i].t=read();
    int l=1,r=m,ans=0;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    if(!ans) printf("0\n");
    else printf("-1\n%d",ans);
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/172062.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • tensorflow所有版本_tensorflow最新版本

    tensorflow所有版本_tensorflow最新版本https://pypi.org/project/tensorflow-gpu/1.13.0/#files把13改对你想要的版本

  • 适配器Adapter[通俗易懂]

    适配器Adapter[通俗易懂]适配器Adapter动机模式定义实例结构要点总结笔记动机在软件系统中,由于应用环境的变化,常常需要将”一些现存的对象”放在新的环境中应用.但是新的环境要求的接口是这些现存对象所不满足的.如何应对这种”迁移的变化”?如何既能利用现有对象的良好实现,同时又能满足新的应用环境所要求的接口?模式定义将一个类的接口转换为客户希望的另一个接口.Adapter模式使得原本由于接口不兼容而不能在一起工作的那些类可以一起工作实例//目标接口(新接口)class ITarget{public: vir

  • NVL与NVL2函数

    NVL与NVL2函数NVL(EXPER1,EXPER2)表示:如果1为空则显示expre2;否则显示expres1;Eg:NVL(‘test’,’周五’)返回结果:test注意:EXPER1,EXPER2数据类型(NVL要求第二个参数类型可以转换为第一个参数类型)selectnvl(12,’a’)fromdual;报错:ORA-01722:无效数字selectnvl(12,

  • leetcode-1840. 最高建筑高度

    leetcode-1840. 最高建筑高度在一座城市里,你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。这座城市对这些新建筑有一些规定:每栋建筑的高度必须是一个非负整数。第一栋建筑的高度 必须 是 0 。任意两栋相邻建筑的高度差 不能超过 1 。除此以外,某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出,其中 restrictions[i] = [idi, maxHeighti] ,表示建筑 idi 的高度 不能超过 maxHeighti 。题目保证每栋建筑在 res

  • Cocos图片加密与解密

    Cocos图片加密与解密现在做的cocos项目没有对资源进行加密处理,发布出来的APK一旦被人解包,则所有图片资源都会暴露出来,为了避免图片资源被人恶意使用,所有我准备给自己项目中使用到的图片进行简单加密,这样可以防住一部分解包伸手党。我们这里采用最常见的**异或加密**,*异或加密性质:一个数异或同一个数两次,得到的是本身*。根据这个性质,我们可以采用把图片的字节流进行异或加密,只需要设置一个Key,在本地客户端使用…

  • mysql经纬度查范围内_sql语句查询经纬度范围「建议收藏」

    mysql经纬度查范围内_sql语句查询经纬度范围「建议收藏」最近在做查询指定经纬度范围的数据;问题不知如何下手,于是网上找了点资料,其中有些不懂的地方希望大家能给点想法!问题是这样的:sql语句查询经纬度范围指定一个经纬度,给定一个范围值(单位:千米),查出在经纬度周围这个范围内的数据。经度:113.914619纬度:22.50128范围:2kmlongitude为数据表经度字段latitude为数据表纬度字段SQL在mysql下测试通过,其他数据库可能需…

    2022年10月24日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号