洛谷題目頁面傳送門 & CodeForces題目頁面傳送門
給定一個\(n\)個單詞的文本，第\(i\)個單詞的長度為\(len_i\)，要求截取文本的一段（單詞必須取整的），分若干行放，同行單詞用空格分隔，使得每行的長度不超過\(m\)，最多放\(s\)行，求截取的單詞數最多的截法，
\(n\in\left[1,10^6\right],\sum\limits_{i=1}^nlen_i\in\left[1,5\times10^6\right],ms\in\left[1,10^6\right]\)，
這道題想要AC還是很容易的，考慮列舉截取的第\(1\)個單詞，然后計算往后最多能延申多少個單詞，最后取個\(\max\)，重點在于如何計算往后最多能延申多少個單詞，這個可以傻傻地貪心，先求出\(spl\)陣列，表示從第\(i\)個單詞開始最多能往后延申到第\(spl_i-1\)個單詞放在一行，很顯然，“是否能延申到第\(x\)個單詞放在一行”具有單調性，于是\(spl\)陣列可以\(\mathrm O(n\log n)\)配合前綴和二分求出，那么從第\(i\)個單詞往后最多能延申的單詞數就是\(\underbrace{spl_{spl_{spl_{\cdots_{i}}}}}_{s\text{次}spl\text{映射}}-i\)，這個又顯然可以總共\(\mathrm O(n\log n)\)倍增求出，于是\(\mathrm O(n\log n)\)的復雜度是extremely easy的，
而我們是追求完美的OIer，這個復雜度能否達到\(\mathrm O(n)\)呢？帶\(\log\)復雜度的地方有\(2\)個——求\(spl\)陣列和\(s\)次\(spl\)映射，我們一個一個來看，
首先是求\(spl\)陣列，不難發現，\(spl\)陣列本身具有單調性，即\(spl_i\le spl_{i+1}\)，那么我們可以從后往前two-pointers，求\(spl_i\)時，只需從\(spl_{i+1}\)到\(i\)從后往前試是否能延申到即可，其中邊界是\(spl_{n+1}=n+1\)，這樣所有單詞均攤被試\(\mathrm O(n)\)次，時間復雜度就沒有\(\log\)了，
接下來是映射，仍然利用\(spl\)陣列的單調性，若在所有\(i\)和\(spl_i\)之間連一條邊，若\(i=spl_i\)則不連邊，那么一定會形成一個森林，而對\(i\)進行\(s\)次映射顯然就等于節點\(i\)的\(\min(s,dep_i)\)輩祖先，我們對森林里的每一棵樹進行DFS，同時維護一個遞回堆疊\(stk\)，那么\(\mathrm O(1)\)便可找到節點\(i\)的\(\min(s,dep_i)\)輩祖先，復雜度也變成整體\(\mathrm O(n)\)了，
下面貼代碼：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1000000;
int n/*單詞數*/,m/*每行最多能放的長度*/,s/*最多能放的行數*/;
string a[N+1];//單詞們
int Sum[N+1];//前綴長度和（每個單詞后面加上空格）
vector<int> son[N+2];int fa[N+2];//樹，fa即spl陣列
int stk[N+1],top;//遞回堆疊
int ans[N+2];//從第i個單詞開始最多能延伸的單詞數
void dfs(int x){//對樹DFS
stk[top++]=x;//將此節點入堆疊
ans[x]=stk[max(0,top-1-s)]-x;//O(1)找min(s,dep[i])輩祖先
for(int i=0;i<son[x].size();i++){
int y=son[x][i];
dfs(y);
}
top--;//出堆疊
}
int main(){
cin>>n>>s>>m;
for(int i=1;i<=n;i++)cin>>a[i],Sum[i]=Sum[i-1]+a[i].size()+1/*預處理前綴和*/;
fa[n+1]=n+1;//遞推邊界
for(int i=n;i;i--){//從后往前遞推
fa[i]=fa[i+1];
while(Sum[fa[i]-1]-Sum[i-1]-1>m)fa[i]--;//從后往前試
if(fa[i]!=i)son[fa[i]].pb(i);//連邊
}
// for(int i=1;i<=n+1;i++)cout<<fa[i]<<" ";puts("");
for(int i=1;i<=n+1;i++)if(fa[i]==i)top=0,dfs(i);//DFS每棵樹
int mx=*max_element(ans+1,ans+n+2);//最大答案
for(int i=1;i<=n+1;i++)if(ans[i]==mx){
while(s--){//輸出
for(int j=i;j<fa[i];j++)cout<<a[j]<<(j<fa[i]-1?" ":"\n");
i=fa[i];
}
return 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/96297.html
標籤：C++