題目鏈接：點擊查看

題目大意：給出n個數列，每行放一個，現在指定一個寬度w，滿足w不小于n個數列中最長的那個數列的長度，現在可以將n個數列都放入到一個n*w的矩形之中，每個數列可以在各自的行內左右移動，現在問對于每一列i，求出權值和的最大值，注意，若一個數列的長度小于w，那么其余的位置都用0補齊

題目分析：題目還是比較好懂的，因為給出的圖片以及樣例算是比較友好的了，看看圖片就知道答案是怎么來的了。。讀懂題目之后相當于一個中等難度偏下的模擬，我們只需要照做就好了

具體實現方法就是在輸入的時候，對于每個數字當前的位置記錄一下可貢獻的區間，也就是通過移動可到達的最左和最后的位置，最左邊的答案用in數組儲存，最右邊的答案用out數組儲存，記錄好后開始模擬，我們可以使用一個優先隊列獲得區間中的最大值，最外層的for枚舉的是1~w的列的下標，內層for枚舉的是1~n的行的下標，每次更新時將in數組內的數扔進去，將out數組內的數刪掉，之后就可以直接得到答案了

不過上述方法的時間復雜度是n*w*logw級別的，在這個題目中是不可行的，所以我們必須想辦法優化一下，而且在優先隊列中也不支持隨機訪問和隨機刪除，所以我們可以用multiset來代替優先隊列，每次插入也是logn級別的，而且可以支持find函數查找某個值的位置，以及搭配erase函數刪除掉某個特定的值，剛好滿足上面的操作了

至于優化的話，我們其實每次不必枚舉到1~n，因為1~n的每一行在特定的第i列下，絕大部分都是對答案沒有貢獻的，也就是in數組和out數組在當前列的貢獻為0，這樣的話我們就可以將in和out數組的下標用列來表示，并將其設置為vector容器，這樣就能每次只需要遍歷in[i].size()+out[i].size()個變量了，從O(n)下降到了O(in[i].size()+out[i].size())了，因為題目保證了數組的總長度小于等于1e6，所以我們就完美的將n*w*logw的時間復雜度下降到了w*logw了，也就可以解決這個問題了

這個題目主要還是練習了multiset的使用吧，有一說一，確實蠻好用的，關于multiset我們需要注意一下，若我們要取得最后那個數，應該調用rbegin()而不是end()函數，因為end函數返回的是超尾，如果實在想用end的話可以改成end()-1，所以我們還是直接用rbegin()調用最后一個元素就好了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;struct Node {int val,pos;Node(int VAL,int POS){val=VAL;pos=POS;} };//保存權值和位置(行)multiset<LL>st[N];//st[行]vector<Node>in[N],out[N];//in[列] out[列]LL ans[N];//ans[列]int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,w;scanf("%d%d",&n,&w);for(int i=1;i<=n;i++){int len;scanf("%d",&len);if(len<w)//空白地方可以補0 {in[1].push_back(Node(0,i));out[w-len].push_back(Node(0,i));in[len+1].push_back(Node(0,i));out[w].push_back(Node(0,i));}for(int j=1;j<=len;j++)//維護in數組和out數組{int num;scanf("%d",&num);in[j].push_back(Node(num,i));out[w-len+j].push_back(Node(num,i));}}for(int i=1;i<=w;i++)//枚舉列數 st[行數]{ans[i]=ans[i-1];//因為每次答案可以在前置答案的基礎上操作，避免了多余的操作for(int j=0;j<in[i].size();j++)//枚舉行數 ans[列數]{int pos=in[i][j].pos;//行 int val=in[i][j].val;//值 if(st[pos].size())//如果存在區間最大值，則減去ans[i]-=*st[pos].rbegin();st[pos].insert(val);//更新區間最大值(插入一個值)ans[i]+=*st[pos].rbegin();//再加上區間最大值}for(int j=0;j<out[i-1].size();j++)//注意這里要用out[i-1]來維護ans[i]{int pos=out[i-1][j].pos;//行 int val=out[i-1][j].val;//值 ans[i]-=*st[pos].rbegin();//因為每個out前面必定對應著一個in，所以必定存在區間最大值，直接減去st[pos].erase(st[pos].find(val));//更新區間最大值(刪除一個值)if(st[pos].size())//如果刪除后還存在區間最大值的話，直接加上ans[i]+=*st[pos].rbegin();}}for(int i=1;i<=w;i++)printf("%lld ",ans[i]);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1208E Let Them Slide(模拟+multiset)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。