f160 - 1. 音檔剪輯
題目描述
題目給定音檔的總長度 t，以及 n 個音檔片段的長度。目標是將這些音檔片段串接起來，並盡可能減少分割音檔的次數。每次分割音檔需要額外的時間 s。要求計算最少需要分割的次數。
解題思路
這題可以使用貪心演算法來解決。我們從第一個音檔片段開始，記錄目前剩餘的時間 c。對於每個後續的音檔片段，如果片段長度大於剩餘時間 c，則需要進行分割，將剩餘時間重置為 t，並將分割次數加一。否則，直接從剩餘時間中扣除片段長度。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#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>
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(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int t(read()),n(read()),s(read()),s2,ans=1,c=t;
n--;
while(n--){
s2=read();
if(s2>c){
c=s+t;
++ans;
}
s=s2;
}
write(ans);
}