Codeforces Global Round 13 C. Pekora and Trampoline
原題傳送門
題目大意
告訴你公園里有n個蹦床，每個蹦床有一個能量值Si， 當你跳上第i個蹦床后，你會跳向第i+Si 個蹦床，并且Si 會減1如果它大于1的話，但是如果i+Si大于n，那么就會停止這趟奇妙的旅行，否則，他將繼續按照這個規則跳下去，直到停止，然后題目問你的是求將所有的Si 變成1所需要的最少的旅行次數，
分析：這題因為資料較小，所以O(n2 )也能過，這里給出一個O(n)的解法，不是dsu，那個我不會，具體用差分來做，
1.首先我們來貪心♂的考慮這件事情，注意到我們是為了把所有的Si 變成1，對于已經變成1的如果我們跳上去，只會一個一個的向右側移動，直到遇到第一個不為1的Si ，我們來考慮如果跳上一個蹦床對整體產生的貢獻，顯然，它會讓本身的Si 減1，并且讓它路徑上所有的Sj>1的點減1；這些點一定在它的右側，所以Si 對整體產生的貢獻一定都在該點本身以及向右的位置，如果跳出界的話就只有對本身的貢獻，這樣我們就很清楚的知道，如果一個Si >1并且在i的前面不存在點的能量值大于1，則對該點的減小操作有且僅能從該點出發，執行Si -1次操作，
2.我們知道，一旦我們跳上一個蹦床，它后面的路徑就已經被確定了，換句話說，一個路徑可以由該路徑的起始點來表示，這個很顯然，接著我們再繼續1的思考，對于第一個Si >1的i來講，這Si -1次操作會讓它從自身出發跳到的點的位置逐漸偏左，第一次從Si 出發跳到的第一個點是Si +i，第二次則是Si +i-1…最后一次便是Si +2，如果他的Si 已經為1就沒必要繼續操作了，所以最后一次一定是在Si +2，那么該點所需要的最小操作次數為Si -1次，
3.那么問題來了，我們要如何記錄這些資訊，又要如何處理呢，如果我們按照上述操作，第一個Si 處理完畢后，如果在這個Si 后面還有大于1的點(從Si 出發的路徑對整體的貢獻先咕咕咕)，我們就要分析從Si 出發的所有路徑中是否有點被路徑覆寫，如果沒有，我們就繼續1，2的操作，如果有，我們就必須記錄并處理這些資訊，我們在2中已經分析過，一個路徑可以由一個起始點來表示，那么Si 產生的路徑便是從Si+2一直到Si +i-1，我們給這些點打上一個標記，考慮到是區間，所以我們很自然的就能想到利用差分陣列，我們維護一個差分陣列d，兩端打上標記，如果越界就打到n+1，
這樣我們在從左往右遍歷點的時候，利用差分求前綴和，就知道目前點白嫖的旅行有多少次，如果目前白嫖的旅行次數大于等于了Sj ，那么這個點一定已經變成了1，對于溢位的部分就讓它向右走，因為它只能跳一格了，它已經跳不動了，這樣給后面兩個點再打上差分標記，
但是如果白嫖的不夠厲害，我自己還要付出錢去旅行(即這時候又回到1中的情況)，重復上述操作即可，但是可能會有人會問，如果我只是給每個點擴撒得第一個點打上標記，我又不知道他之后能跳幾格，畢竟是在后面得先跳，可能會跳到重復的點，不，這沒有任何關系，我們從左往右遍歷的時候，一定能知道當前點的白嫖次數，這就足夠求出，它本身能跳到的下一個的點的集合，因為Sj只能一點一點的變小，每次只能減1，即使后面的點先跳，我們只要知道那個點到底白嫖了幾次，就足以求出每個點必要的旅行費用，
如果我們直接分析一個點，假設它前面的點都已經處理完畢了，那么當前的點的被前面所覆寫的次數，便是白嫖次數，對于當前點的每一次旅行，它的下一個點總是確定的，所以我們只需要搜集一個左側的資訊，就一定能推出當前點的資訊，從而推至右側，
萌新(沒有萌新實力的菜雞)第一次發題解，寫的邏輯不是很好，求各位大佬照顧，輕噴，主要是為了鞏固而用的，
以下是代碼
#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
ll t,n,m,q,u,v;
ll s[N],d[N];
void solve(){
cin>>n;
for(int i = 1;i <= n;++i){cin>>s[i];d[i] = 0;}
ll ans = 0;
for(int i = 1;i <= n;++i){
d[i] += d[i-1];
++d[i+2],--d[min(n,s[i]+i)+1];
if(d[i] >= s[i])d[i+1] += d[i] - s[i] + 1, d[i+2] -= d[i] - s[i] + 1;
s[i] = max(s[i]-d[i],1ll);
ans += s[i] - 1;
}
cout<<ans<<endl;
}
int main() {
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
cin>>t;
while(t--){
solve();
}
fclose(stdin);
fclose(stdout);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/265488.html
標籤：其他