CSU 1335: 高桥和低桥(扫描线) 13年省赛题

2024-05-12 20:18

本文主要是介绍CSU 1335: 高桥和低桥(扫描线) 13年省赛题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1335: 高桥和低桥

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 957   Solved: 279
[ Submit][ Status][ Web Board]

Description

有个脑筋急转弯是这样的:有距离很近的一高一低两座桥,两次洪水之后高桥被淹了两次,低桥却只被淹了一次,为什么?答案是:因为低桥太低了,第一次洪水退去之后水位依然在低桥之上,所以不算“淹了两次”。举例说明:

假定高桥和低桥的高度分别是5和2,初始水位为1

第一次洪水:水位提高到6(两个桥都被淹),退到2(高桥不再被淹,但低桥仍然被淹)

第二次洪水:水位提高到8(高桥又被淹了),退到3。

没错,文字游戏。关键在于“又”的含义。如果某次洪水退去之后一座桥仍然被淹(即水位不小于桥的高度),那么下次洪水来临水位提高时不能算“又”淹一次。

输入n座桥的高度以及第i次洪水的涨水水位ai和退水水位bi,统计有多少座桥至少被淹了k次。初始水位为1,且每次洪水的涨水水位一定大于上次洪水的退水水位。

Input

输入文件最多包含25组测试数据。每组数据第一行为三个整数n, m, k(1<=n,m,k<=105)。第二行为n个整数hi(2<=hi<=108),即各个桥的高度。以下m行每行包含两个整数ai和bi(1<=bi<ai<=108, ai>bi-1)。输入文件不超过5MB。

Output

对于每组数据,输出至少被淹k次的桥的个数。

Sample Input

2 2 22 56 28 35 3 22 3 4 5 65 34 25 2

Sample Output

Case 1: 1Case 2: 3

HINT

Source

湖南省第九届大学生计算机程序设计竞赛


#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 100010 ;
int num[N],h[N];
int two(int n, int ans)
{int l=1 , r=n , mid ;while(l<=r){mid=(l+r)>>1;if(h[mid]>=ans)r = mid-1;elsel = mid+1;}return l;
}
int main()
{int n,m,k;int T = 0;while(scanf("%d%d%d",&n,&m,&k)>0){memset(num , 0 , (n+3)*sizeof(int));for(int i=1; i<=n; i++)scanf("%d",&h[i]);sort(h+1, h+1+n);int a ,b ,th=2 , id;while(m--){scanf("%d%d",&a,&b);id = two(n , th);num[id]++ ;id = two(n , a+1 );num[id]--;th = b+1;}int ans = 0 , ad= 0;for(int i=1; i<=n; i++){ad += num[i] ;if(ad>=k)ans++;}printf("Case %d: %d\n",++T,ans);}
}

这篇关于CSU 1335: 高桥和低桥(扫描线) 13年省赛题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

13 transition数组的动画使用

划重点 动画:transitiontransition-group :数组动画数组的 添加 / 删除 豆腐粉丝汤 清淡又健康 <!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><me

【CTF Web】BUUCTF Upload-Labs-Linux Pass-13 Writeup(文件上传+PHP+文件包含漏洞+PNG图片马)

Upload-Labs-Linux 1 点击部署靶机。 简介 upload-labs是一个使用php语言编写的,专门收集渗透测试和CTF中遇到的各种上传漏洞的靶场。旨在帮助大家对上传漏洞有一个全面的了解。目前一共20关,每一关都包含着不同上传方式。 注意 1.每一关没有固定的通关方法,大家不要自限思维! 2.本项目提供的writeup只是起一个参考作用,希望大家可以分享出自己的通关思路

Chapter 13 普通组件的注册使用

欢迎大家订阅【Vue2+Vue3】入门到实践 专栏,开启你的 Vue 学习之旅! 文章目录 前言一、组件创建二、局部注册三、全局注册 前言 在 Vue.js 中,组件是构建应用程序的基本单元。本章详细讲解了注册和使用 Vue 的普通组件的两种方式:局部注册和全局注册。 本篇文章参考黑马程序员 一、组件创建 ①定义 Vue 组件是一种具有特定功能的 Vue 实

VMware Fusion Pro 13 Mac版虚拟机 安装Win11系统教程

Mac分享吧 文章目录 Win11安装完成,软件打开效果一、VMware安装Windows11虚拟机1️⃣:准备镜像2️⃣:创建虚拟机3️⃣:虚拟机设置4️⃣:安装虚拟机5️⃣:解决连不上网问题 安装完成!!! Win11安装完成,软件打开效果 一、VMware安装Windows11虚拟机 首先确保自己的mac开启了网络共享。不然虚拟机连不上👀的 1️⃣:准备镜像

华为 HCIP-Datacom H12-821 题库 (13)

有需要题库的可以看主页置顶 1.可以携带外部路由的 tag 标签信息的是以下哪一类 LSA? A、4 类 LSA B、5 类 LSA  C、3 类 LSA  D、2 类 LSA 答案:B 解析: 暂无解析 2..两台路由器直连,并设定网络类型为 p2p 建立OSPF 邻居。那么两台路由器传输 OSPF 报文的目的 IP 地址是以下哪一项? A、使用组播地址 224.0.0.6 B

[情商-13]:语言的艺术:何为真实和真相,所谓真相,就是别人想让你知道的真相!洞察谎言与真相!

目录 前言: 一、说话的真实程度分级 二、说谎动机分级:善意谎言、中性谎言、恶意谎言 三、小心:所谓真相:只说对自己有利的真相 四、小心:所谓真相:就是别人想让你知道的真相 五、小心:所谓善解人意:就是别人只说你想要听到的话 前言: 何为真实和真相,所谓真相,就是别人想让你知道的真相!洞察谎言与真相! 人与人交流话语中,处处充满了不真实,完全真实的只是其中一小部分,这

C++笔试强训12、13、14

文章目录 笔试强训12一、选择题1-5题6-10题 二、编程题题目一题目二 笔试强训13一、选择题1-5题6-10题 二、编程题题目一题目二 笔试强训14一、选择题1-5题6-10题 二、编程题题目一题目二 笔试强训12 一、选择题 1-5题 引用:是一个别名,与其被引用的实体公用一份内存空间,编译器不会给引用变量单独开辟新的空间。A错误 故选A。 A