網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
區(qū)間問(wèn)題
區(qū)間選點(diǎn)
給定 N 個(gè)閉區(qū)間 [ai,bi]，請(qǐng)你在數(shù)軸上選擇盡量少的點(diǎn)，使得每個(gè)區(qū)間內(nèi)至少包含一個(gè)選出的點(diǎn)。
輸出選擇的點(diǎn)的最小數(shù)量。
位于區(qū)間端點(diǎn)上的點(diǎn)也算作區(qū)間內(nèi)。
輸入格式
第一行包含整數(shù) N，表示區(qū)間數(shù)。
接下來(lái) N 行，每行包含兩個(gè)整數(shù) ai,bi，表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù)，表示所需的點(diǎn)的最小數(shù)量。
數(shù)據(jù)范圍
1≤N≤1e5,
?1e9≤ai≤bi≤1e9
先對(duì)右端點(diǎn)進(jìn)行排序，有交集的區(qū)間進(jìn)行右端點(diǎn)的更新，沒(méi)有交集則點(diǎn)數(shù)+1。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int a,b;
bool operator<(const node&w)const {
return b<w.b;}
}range[N];
int main(){
int n;
cin>>n;
int a,b;
for(int i=0;i<n;i++){
cin>>a>>b;
range[i]={a,b};
}
sort(range, range+n);
int s=-2e9,cnt=0;
for(int i=0;i<n;i++){
if(s<range[i].a){
cnt++;
s=range[i].b;
}
}
cout<<cnt;
return 0;
}
最大不相交區(qū)間數(shù)量
給定 N 個(gè)閉區(qū)間 [ai,bi]，請(qǐng)你在數(shù)軸上選擇若干區(qū)間，使得選中的區(qū)間之間互不相交（包括端點(diǎn)）。
輸出可選取區(qū)間的最大數(shù)量。
輸入格式
第一行包含整數(shù) N，表示區(qū)間數(shù)。
接下來(lái) N 行，每行包含兩個(gè)整數(shù) ai,bi，表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù)，表示可選取區(qū)間的最大數(shù)量。
數(shù)據(jù)范圍
1≤N≤1e5,
?1e9≤ai≤bi≤1e9
先對(duì)右端點(diǎn)進(jìn)行排序，有交集的區(qū)間進(jìn)行右端點(diǎn)的更新，沒(méi)有交集則點(diǎn)數(shù)+1。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
int a,b;
bool operator<(const node&w)const{
return b<w.b;
}
}range[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
range[i]={a,b};
}
int res=0,s=-2e9;
sort(range,range+n);
for(int i=0;i<n;i++){
if(range[i].a>s){
s=range[i].b;
res++;
}
}
cout<<res;
return 0;
}
區(qū)間分組
給定 N 個(gè)閉區(qū)間 [ai,bi]，請(qǐng)你將這些區(qū)間分成若干組，使得每組內(nèi)部的區(qū)間兩兩之間（包括端點(diǎn)）沒(méi)有交集，并使得組數(shù)盡可能小。
輸出最小組數(shù)。
輸入格式
第一行包含整數(shù) N，表示區(qū)間數(shù)。
接下來(lái) N 行，每行包含兩個(gè)整數(shù) ai,bi，表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù)，表示最小組數(shù)。
數(shù)據(jù)范圍
1≤N≤1e5,
?1e9≤ai≤bi≤1e9
先區(qū)分左右端點(diǎn)進(jìn)行排序，再遍歷取左右 端點(diǎn)未抵消的最大值。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int b[2 * N], idx;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
b[idx++] = l * 2;
b[idx++] = r * 2 + 1;//用奇偶性區(qū)分左右端點(diǎn)
}
sort(b, b + idx);
int res = 1, t = 0;
for (int i = 0; i < idx; i++) {
if (b[i] % 2 == 0)t++;
else t--;
res = max(res, t);
}
cout << res;
return 0;
}
優(yōu)先隊(duì)列做法。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
struct Range {
int l, r;
bool operator <(const Range& w)const {
return l < w.l;
}
}range[N];
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
range[i] = { l,r };}
sort(range, range + n);
int res = 0,ed=-2e9;
priority_queue<int, vector<int>, greater<int>>heap;
for (int i = 0; i < n; i++) {
auto r = range[i];
if (heap.empty() || heap.top() >= r.l)heap.push(r.r);
else {
int t = heap.top();
heap.pop();
heap.push(r.r);
}
}
cout << heap.size();
return 0;
}區(qū)間覆蓋
給定 N 個(gè)閉區(qū)間 [ai,bi] 以及一個(gè)線(xiàn)段區(qū)間 [s,t]，請(qǐng)你選擇盡量少的區(qū)間，將指定線(xiàn)段區(qū)間完全覆蓋。
輸出最少區(qū)間數(shù)，如果無(wú)法完全覆蓋則輸出 ?1。
輸入格式
第一行包含兩個(gè)整數(shù) s 和 t，表示給定線(xiàn)段區(qū)間的兩個(gè)端點(diǎn)。
第二行包含整數(shù) N，表示給定區(qū)間數(shù)。
接下來(lái) N 行，每行包含兩個(gè)整數(shù) ai,bi，表示一個(gè)區(qū)間的兩個(gè)端點(diǎn)。
輸出格式
輸出一個(gè)整數(shù)，表示所需最少區(qū)間數(shù)。
如果無(wú)解，則輸出 ?1。
數(shù)據(jù)范圍
1≤N≤1e5,
?1e9≤ai≤bi≤1e9,
?1e9≤s≤t≤1e9
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
struct Range {
int l, r;
bool operator <(const Range& w)const {
return l < w.l;
}
}range[N];
int main() {
int n;
int st, ed;
cin >> st >> ed;
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
range[i] = { l,r };
}
sort(range, range + n);
int res = 0;
bool sc = false;
for (int i = 0; i < n; i++) {
int j = i, r = -2e9;
while (j < n && range[j].l <= st) {
r = max(r, range[j].r);
j++;
}
if (r < st) {
res = -1;
break;
}
res++;
if (r >= ed) {
sc = true;
break;
}
i = j-1;
st = r;
}
if (!sc)cout << -1;
else cout << res;
return 0;
}Huffman樹(shù)
合并果子
在一個(gè)果園里，達(dá)達(dá)已經(jīng)將所有的果子打了下來(lái)，而且按果子的不同種類(lèi)分成了不同的堆。
達(dá)達(dá)決定把所有的果子合成一堆。
每一次合并，達(dá)達(dá)可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。
可以看出，所有的果子經(jīng)過(guò) n?1 次合并之后，就只剩下一堆了。
達(dá)達(dá)在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。
因?yàn)檫€要花大力氣把這些果子搬回家，所以達(dá)達(dá)在合并果子時(shí)要盡可能地節(jié)省體力。
假定每個(gè)果子重量都為 1，并且已知果子的種類(lèi)數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使達(dá)達(dá)耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。
例如有 3 種果子，數(shù)目依次為 1，2，9。
可以先將 1、2 堆合并，新堆數(shù)目為 3，耗費(fèi)體力為 3。
接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為 12，耗費(fèi)體力為 12。
所以達(dá)達(dá)總共耗費(fèi)體力=3+12=15。
可以證明 15 為最小的體力耗費(fèi)值。
輸入格式
輸入包括兩行，第一行是一個(gè)整數(shù) n，表示果子的種類(lèi)數(shù)。
第二行包含 n 個(gè)整數(shù)，用空格分隔，第 i 個(gè)整數(shù) ai 是第 i 種果子的數(shù)目。
輸出格式
輸出包括一行，這一行只包含一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值。
輸入數(shù)據(jù)保證這個(gè)值小于 231。
數(shù)據(jù)范圍
1≤n≤10000,
1≤ai≤20000
只需要用優(yōu)先隊(duì)列先取出兩個(gè)，再插入一個(gè)，直至最后剩下一個(gè)。
#include<iostream>
#include<algorithm>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
priority_queue<int, vector<int>, greater<int>>heap;
while (n--) {
int x;
cin >> x;
heap.push(x);
}
int res = 0;
while (heap.size() > 1) {
int a = heap.top();
heap.pop();
int b = heap.top();
heap.pop();
int c = a + b;
heap.push(c);
res += c;
}
cout << res;
return 0;
}
排序不等式
排隊(duì)打水
有 n 個(gè)人排隊(duì)到 1 個(gè)水龍頭處打水，第 i 個(gè)人裝滿(mǎn)水桶所需的時(shí)間是 ti，請(qǐng)問(wèn)如何安排他們的打水順序才能使所有人的等待時(shí)間之和最小？
輸入格式
第一行包含整數(shù) n。
第二行包含 n 個(gè)整數(shù)，其中第 i 個(gè)整數(shù)表示第 i 個(gè)人裝滿(mǎn)水桶所花費(fèi)的時(shí)間 ti。
輸出格式
輸出一個(gè)整數(shù)，表示最小的等待時(shí)間之和。
數(shù)據(jù)范圍
1≤n≤1e5,
1≤ti≤1e4
值正序，下標(biāo)倒序相乘得到最小值
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
int x=n;
long long res=0;
for (int i = 0; i < n; i++) {
res += a[i] * (x - 1);
x--;
}
cout << res;
return 0;
}
絕對(duì)值不等式
貨艙選址
在一條數(shù)軸上有 N 家商店，它們的坐標(biāo)分別為 A1～AN。
現(xiàn)在需要在數(shù)軸上建立一家貨倉(cāng)，每天清晨，從貨倉(cāng)到每家商店都要運(yùn)送一車(chē)商品。
為了提高效率，求把貨倉(cāng)建在何處，可以使得貨倉(cāng)到每家商店的距離之和最小。
輸入格式
第一行輸入整數(shù) N。
第二行 N 個(gè)整數(shù) A1～AN。
輸出格式
輸出一個(gè)整數(shù)，表示距離之和的最小值。
數(shù)據(jù)范圍
1≤N≤100000,
0≤Ai≤40000
只需統(tǒng)計(jì)各點(diǎn)到中位數(shù)的距離之和。
#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{
cin>>n;
for (i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);//排序
int sm=a[n/2+1];//中位數(shù)
for (i=1;i<=n;i++)
ans=ans+abs(a[i]-sm);//統(tǒng)計(jì)和中位數(shù)之間的差
cout<<ans;
return 0;
}原文鏈接：https://blog.csdn.net/weixin_52465909/article/details/125630088
相關(guān)推薦
- 2022-03-28 Python獲取網(wǎng)絡(luò)時(shí)間戳的兩種方法詳解_python
- 2022-10-27 React?State與生命周期詳細(xì)介紹_React
- 2022-06-10 教你如何獲取Harbor的帶tag的鏡像清單_docker
- 2022-05-21 Python?requests用法和django后臺(tái)處理詳解_python
- 2022-01-15 Meteor 項(xiàng)目部署至服務(wù)器（windows）
- 2022-04-12 C++中的異常實(shí)例詳解_C 語(yǔ)言
- 2023-01-30 Android實(shí)現(xiàn)RecyclerView嵌套流式布局的詳細(xì)過(guò)程_Android
- 2022-03-18 webpack的懶加載和預(yù)加載詳解（webpack按需加載）
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門(mén)
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速