題意：給出一個序列，其實就是一個函數，下標從1開始，把這個函數分解成幾個開關函數G(x, y)的和，分法可以有多種，求各種分法中最小y-x+1的最大值。 ——>>這題，真貪心！ 對於：2 2 2 顯然，分解成3個G(1, 3)時最小長度y-x+1 = 3；如果不是，那麼其最小長度一定比3小——可得——兩數相等的時候，應把它們歸到一個G中。 對於：2 4 2 如果第一步將2, 4歸到一個G,而不要後面的2時，將得到2G(1, 2) + 2G(2, 3)，此時最小長度為2；如果開始時三個數歸到一個G，那麼得到2G(1, 3) + 2G(2, 2)，此時最小長度為1——可得——增大時歸到一個G，減小時不歸到一個G，才能使最小長度最大。 開始時我將輸入的數據存入數組a，對a一次次的a[i]--，一直到所有的a[i] == 0，結果不用說——TLE； 接著，看到對於2 3 3 7 4 1，a[1]到a[4]可以直接-2（左邊第一個最小數2），對於4 4 4 7 4 1，a[1]到a[4]可以直接-3（右邊最大一個 - 右邊的數），用這個方法再來將所有的a[i]減至0，結果一樣——TLE； 可以想到，不能這樣直接將所有的a[i]減至0！！！ ——>>最後，考慮G(L, R)，用m[R]表示a[L]到a[R]要減的量，掃描一次a，維護m與一個左邊最小數要減的temp就好，有點類似線段樹的下傳機制。 [cpp] #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 10000 + 10; int main() { int T, N, i; long long a[maxn], m[maxn]; //a為輸入數組，m[R]表示a[L]到a[R]要減的量 scanf("%d", &T); while(T--) { scanf("%d", &N); for(i = 1; i <= N; i++) scanf("%I64d", &a[i]); a[N+1] = 0; //最後加個0，好處理 int L = 1, R = 1, temp = 0, minn = 2147483647; //G(L, R)，temp為根據後面確定的a[L]要減的量，minn為結果 memset(m, 0, sizeof(m)); while(L <= N) { for(; L <= N; L++) if(!(a[L]-temp)) temp -= m[L]; //更新 else break; //找到第一個不是0的a[L] if(L > N) continue; //完成 if(R < L) R = L; //有可能的，如2 2 2 3 3 for(; R <= N; R++) if(a[R+1] < a[R]-m[R]) //找到右界 { www.2cto.com minn = min(minn, R-L+1); //更新 long long dis = a[R] - m[R] - a[R+1]; //dis個G(L, R) dis = min(dis, a[L]-temp); m[R] += dis; //累加增量 temp += dis; //更新 break; } } printf("%d\n", minn); } return 0; }
