洛谷 火燒赤壁 差分/貪心

題目背景

曹操平定北方以后,公元 208 年,率領大軍南下,進攻劉表。他的人馬還沒有到荊州,劉表已經病死。他的兒子劉琮聽到曹軍聲勢浩大,嚇破了膽,先派人求降了。

孫權任命周瑜為都督,撥給他三萬水軍,叫他同劉備協力抵抗曹操。

隆冬的十一月,天氣突然回暖,刮起了東南風。

沒想到東吳船隊離開北岸大約二里距離,前面十條大船突然同時起火。火借風勢,風助火威。十條火船,好比十條火龍一樣,闖進曹軍水寨。那里的船艦,都擠在一起,又躲不開,很快地都燒起來。一眨眼工夫,已經燒成一片火海。

曹操氣急敗壞的把你找來,要你鉆入火海把連環線上著火的船只的長度統計出來!

題目描述

給定每個起火部分的起點和終點,請你求出燃燒位置的長度之和。

輸入格式

第一行一個整數,表示起火的信息條數?n。
接下來?n?行,每行兩個整數?a,b,表示一個著火位置的起點和終點(注意:左閉右開)。

輸出格式

輸出一行一個整數表示答案。

輸入輸出樣例

輸入 #1復制

3
-1 1
5 11
2 9

輸出 #1復制

11

說明/提示

數據規模與約定

對于全部的測試點,保證?1≤n≤2×104,?231≤a<b<231,且答案小于?231。

代碼1:差分:80分,由于mn和mx的值超過1e8。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MX 20005
using namespace std;
int n;?
int a[MX]= {0},d[MX];
int main() {
cin>>n;
int mn = 1e9+7,mx = -1e9+7;;
while(n--)
{
int x,y;
cin>>x>>y;
d[x] += 1;
d[y] += -1;
mn = min(mn,x);
mx = max(mx,y);
}
int cnt = 0;
for(int i = mn;i <= mx;i++)
{
a[i] = a[i-1] + d[i];
if(a[i])
{
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}

代碼二:模擬

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MX 20005
using namespace std;
int n;?
int a[MX],b[MX];
int main() {
cin>>n;
for(int i = 1;i <= n;i++)
{
cin>>a[i]>>b[i];
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int cnt = 0;
for(int i = 1;i <= n;i++)
{
cnt = cnt + b[i] - a[i];
if(i < n)
{
if(b[i] > a[i+1])
{
cnt = cnt - (b[i] - a[i+1]);
}
}?
}
cout<<cnt<<endl;
return 0;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/917555.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/917555.shtml
英文地址,請注明出處:http://en.pswp.cn/news/917555.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Linux 用戶與組管理全解析

Linux 用戶與組管理一、用戶和組的基本概念 1. 用戶賬號類型 超級用戶&#xff08;root&#xff09;&#xff1a;默認擁有系統最高權限&#xff08;UID0&#xff09;&#xff0c;僅建議用于系統管理與維護&#xff0c;日常操作應使用普通用戶。普通用戶&#xff1a;由管理員創建…

開疆智能ModbusTCP轉Profient網關連接ER機器人配置案例

本案例時西門子1200PLC通過ModbusTCP轉Profinet網關連接埃斯頓機器人的配置案例&#xff0c;網關作為ModbusTCP的客戶端連接機器人。配置過程&#xff1a;首先打開機器人通訊手冊。查詢機器人支持的功能碼及默認IP和端口號打開網關配置軟件“Gateway Configuration Studio”新建…

Docker換源加速(更換鏡像源)詳細教程(2025.3最新可用鏡像,全網最詳細)

文章目錄前言可用鏡像源匯總換源方法1-臨時換源換源方法2-永久換源&#xff08;推薦&#xff09;常見問題及對應解決方案1.換源后&#xff0c;可以成功pull&#xff0c;但是search會出錯補充1.如何測試鏡像源是否可用2.Docker內的Linux換源教程換源速通版&#xff08;可以直接無…

機器學習【三】SVM

本文系統介紹了支持向量機(SVM)的理論與實踐。理論部分首先區分了線性可分與不可分問題&#xff0c;闡述了SVM通過尋找最優超平面實現分類的核心思想&#xff0c;包括支持向量、間隔最大化等關鍵概念。詳細講解了硬間隔與軟間隔SVM的數學原理&#xff0c;以及核函數(線性核、多…

DevOps平臺大比拼:Gitee、Jenkins與CircleCI如何選型?

DevOps平臺大比拼&#xff1a;Gitee、Jenkins與CircleCI如何選型&#xff1f; 在數字化轉型浪潮席卷全球的當下&#xff0c;DevOps已成為企業提升研發效能的關鍵引擎。面對市場上紛繁復雜的DevOps工具鏈&#xff0c;如何選擇最適合自身業務需求的平臺成為技術決策者的重要課題。…

開源醫院信息管理系統:基于若依框架的智慧醫療解決方案

引言在數字化浪潮的推動下&#xff0c;醫療行業正加速向信息化、智能化轉型。醫院信息管理系統&#xff08;HIS&#xff09;作為醫療管理的核心工具&#xff0c;直接影響醫院的運營效率和服務質量。近期&#xff0c;一款基于 若依框架 Vue 的開源醫院管理系統&#xff08;hosp…

我的世界進階模組開發教程——附魔(2)

EnchantmentHelper 類詳解 EnchantmentHelper 是 Minecraft 中處理物品附魔邏輯的核心工具類,提供附魔的存儲、查詢、計算和應用等功能。以下是對其字段和方法的逐行詳細解釋: 關鍵字段 private static final String TAG_ENCH_ID = "id"; // NBT標簽鍵:附…

深度學習零基礎入門(4)-卷積神經網絡架構

許久不見~ 本節我們延續上一節的話題來看看卷積神經網絡的架構&#xff0c;看看具體的卷積、池化等操作卷積神經網絡詳解&#xff1a;從基礎操作到整體架構 一、卷積操作&#xff1a;特征提取的核心 卷積是卷積神經網絡&#xff08;CNN&#xff09;的核心操作&#xff0c;靈感來…

C語言的控制語句

C的控制語句 控制語句是C語言中用于控制程序執行流程的結構。通過控制語句,可以根據條件執行不同的代碼塊,或者重復執行某些操作,從而實現復雜的邏輯和功能。掌握控制語句是編寫有效和高效C程序的關鍵。 1 條件控制 條件控制語句用于根據某些條件來決定程序的執行路徑。C語…

Mac電腦基本功能快捷鍵

1. 個性化桌面 將喜愛照片添加為桌面墻紙。前往“系統設置”&#xff0c;然后點按邊欄中的“墻紙”。點按“添加照片”&#xff0c;然后從文件或“照片”App選取一張照片。 2. 截屏 按下鍵盤上的Shift &#xfffc; Command ? 5&#xff0c;然后選取捕捉整個屏幕、App窗口或…

微算法科技(NASDAQ: MLGO)開發量子邊緣檢測算法,為實時圖像處理與邊緣智能設備提供了新的解決方案

圖像邊緣檢測是計算機視覺的核心任務&#xff0c;傳統算法&#xff08;如 Sobel、Canny&#xff09;依賴梯度計算與閾值分割&#xff0c;在處理高分辨率、復雜紋理圖像時面臨計算效率瓶頸。隨著量子計算技術的發展&#xff0c;利用量子態疊加與并行處理特性&#xff0c;微算法科…

斷點續傳Demo實現

基于我們的DownloadManager.swift代碼&#xff0c;讓我詳細解釋斷點續傳需要實現的核心功能&#xff1a; 斷點續傳的核心實現要素 1. 后臺會話配置 private func setupBackgroundSession() {let config URLSessionConfiguration.background(withIdentifier: "com.test.do…

《Leetcode》-面試題-hot100-子串

題目列表 560. 和為K的子數組 中等難度 leetcode鏈接 239 滑動窗口最大值 困難難度 leetcode鏈接 76 最小覆蓋子串 困難難度 leetcode鏈接 題目 &#xff08;1&#xff09;和為K的子數組 給你一個整數數組 nums 和一個整數 k &#xff0c;請你統計并返回 該數組中和為 …

點擊彈框以外的區域關閉彈框

在 Vue 3 中&#xff0c;如果你想判斷點擊的目標是否在彈框內&#xff0c;可以通過以下步驟實現。這里我們將使用 ref 來引用彈框組件&#xff0c;并在點擊事件中進行判斷。 示例代碼 1. 創建彈框子組件 首先&#xff0c;創建一個名為 Modal.vue 的子組件。 <!-- Modal.vue …

00.Vue基礎入門【小白級別手把手!】

目錄 一、Vue介紹 二、創建Vue項目 nodeJs nvm版本管理 創建Vue項目 VS Code編輯器 三、.Vue文件結構說明 數據渲染 四、Vue項目目錄說明 main.ts文件說明 五、Vue官網文檔學習 一、Vue介紹 基礎介紹 Vue是一個前端Web框架&#xff0c;屬于單頁應用&#xff08;SPA&am…

將Varjo XR技術融入戰斗機訓練模擬器,有效提升模擬訓練沉浸感與效率

本周在Varjo總部&#xff0c;收到了一份令人興奮的禮物&#xff0c;一架由Dogfight Boss與varjo XR-4集成的訓練模擬器。這是一個專業級模擬器&#xff0c;專為高保真訓練和任務排練而設計&#xff0c;非常注重細節&#xff0c;提高了沉浸水平。為此Dogfight Boss的首席執行官L…

C# async await 實現機制詳解

一、async/await 異步編程實現機制 1.1 核心概念 async/await 是 C# 5.0 引入的語法糖&#xff0c;它基于**狀態機&#xff08;State Machine&#xff09;**模式實現&#xff0c;將異步方法轉換為編譯器生成的狀態機類。 1.2 編譯器轉換過程 當編譯器遇到 async 方法時&#xf…

Servlet 學習筆記

本文為記錄Servlet學習時的一些筆記和代碼 課程參考黑馬程序員 對于Java Web 學習的一個復習一 概述server applet 運行在服務器端的小程序 本質就是一個接口 定義java類被瀏覽器訪問到&#xff08;Tomcat識別&#xff09;的規則我們會自定義這樣一個類來實現復寫方法實現接口二…

【maven】倉庫配置

目錄 一、本地倉庫 二、私有倉庫 三、阿里云倉庫 一、本地倉庫 針對無外網、無maven私服&#xff0c;只有本地倉庫&#xff0c;進行maven項目開發。在maven的settings.xml中設置三項&#xff1a; 1、本地倉庫地址 默認在當前系統用戶下創建目錄&#xff1a;.m2/repository…

信息系統架構設計的系統性解析

一、信息系統架構設計??概念定義??&#xff1a;信息系統架構&#xff08;ISA&#xff09;是對系統組件、交互關系及環境約束的結構化抽象&#xff0c;確保業務目標與技術實現對齊。核心要素包括業務邏輯層、數據層、應用層和基礎設施層。??設計方法??&#xff1a;??T…