f607 - 3. 切割費用
題目描述
題目描述一根長度為 L 的棍子，被切割 n 次。每次切割的位置給定，切割費用等於被切割棍子的長度。要求計算總切割費用。
解題思路
這題可以使用貪心策略來解決。首先，將所有切割點按照數值大小排序。然後，使用一個集合 (set) 來儲存已經切割過的點，初始時包含棍子的起點 0 和終點 L。對於每個切割點，找到集合中比它小的最大值和比它大的最小值，切割費用就是這兩個值之間的距離。將切割點插入集合，重複此過程直到所有切割點都被處理。使用 set 的 lower_bound 和 lower_bound - 1 可以高效地找到所需的值。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序和 set 的插入/查找操作)
- 空間複雜度: O(n) (主要來自 set 儲存切割點)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <set>
using namespace std;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(long long int x) {
if(x==0)
putchar_unlocked('0');
else{
long long int stk[15],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
set <int> a;
set <int>::iterator it;
int n=read(),l=read(),x,y,b[n]={0};
long long int ans=0;
for(int i=0;i<n;++i){
x=read();
y=read();
b[y-1]=x;
}
a.insert(0);
a.insert(l);
for(long long int i=0;i<n;++i){
it=a.lower_bound(b[i]);
ans+=*it-*--it;
a.insert(b[i]);
}
write(ans);
}