題意

給定正整數 \(N, L\) 和一個長度為 \(N\) 的正整數序列 \(A = (A_1, A_2, \dots, A_N)\)。

對于 \(i = 1, 2, \dots, N\)，請回答以下問題：

是否存在一個長度為 \(L\) 的非負整數序列 \(B = (B_1, B_2, \dots, B_L)\)，使得

\[\sum_{j=1}^{L-1} \sum_{k=j+1}^{L} |B_j - B_k| = A_i \]

如果存在，請求出所有滿足條件的 \(B\) 中 \(\max(B)\) 的最小值；如果不存在，請輸出 \(-1\)。

• \(1 \leq N \leq 2 \times 10^5\)
• \(2 \leq L \leq 2 \times 10^5\)
• \(1 \leq A_i \leq 2 \times 10^5\)
• 輸入均為整數

怎么做

這道題本來我發現了單調性，想著能不能二分，然后發現我就是個弱智。

既然沒有想法，就先去找性質把。

我們發現 \(B\) 的順序不會影響結果，而這個絕對值符號讓我們束手束腳的。

我們故假設 \(B\) 是單調不降的。

為了方便，我們記 \(A[i]\) 為 \(val\)，因為我不喜歡使用 \(k\)。

這樣問題就成了 \(\sum_{i=1}^{L-1}\sum_{j=i+1}^{L}(B_j-B_i)\)。

我們又發現 \(B[1]\) 一定要是 \(0\) 才能使問題答案最優。

如果我們知道相鄰兩項差擴大或著減小的貢獻就好了。

我們猛地發現了一個神奇的事情，那就是我們既然規定了 \(B\) 單調不降，那么我們的每一次計算實際上就可以被一大堆相鄰項的差所表示。

比如說我們計算的 \(B_j-B_i\)。

這個就可以表示為 \((B_j-B_{j-1})+(B_{j-1}-B_{j-2})+......\) 像一個區間一樣把其中的一些點加起來。

我們考慮一對相鄰項會被貢獻多少次。

我們發現這個次數是固定的，我們統計區間數量，也就是左端點可以存在的地方和右端點可以存在的地方乘起來。

最后我們可以得出這個問題可以變成 \(\sum_{i=1}^{L-1}i(L-i)(B_{i+1}-B_i)\)

這個我們就可以看作一個背包問題來進行考慮了。

重量是 \(i(L-i)\)，價格是 \(1\)。

我們做完全背包就行了。

代碼如下

#include <bits/stdc++.h>
using namespace std;
namespace BaiBaiShaFeng{
	const int MN=1e6+116;
	int v[MN], w[MN], dp[MN];
	void solve(int N, int L, int A[]){
		memset(dp,0x3f,sizeof(dp)); dp[0]=0;
		for(int j=1; j*(L-j)<MN&&j<L; ++j){
			for(int i=j*(L-j); i<MN; ++i){
				dp[i]=min(dp[i],dp[i-j*(L-j)]+1);
			}
		}
		for(int i=1,val; i<=N; ++i){
			if(dp[A[i]]==0x3f3f3f3f) cout<<-1<<'\n';
			else cout<<dp[A[i]]<<'\n';
		}
	}
}
const int MN=1e6+116;
int n, l, a[MN];
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>l; for(int i=1; i<=n; ++i) cin>>a[i];
	BaiBaiShaFeng::solve(n,l,a);
	return 0;
}