ProblemE The League of Sequence Designers(數論 Math theorm)

題目大意：

有一公式\( \max(r - l + 1 ) \cdot \sum_{l \leq i \leq n } a_{i} , 其中 1 \leq l \leq r \leq n \)
題目給予一貪心演算法，但此演算法並不正確。演算法如下:

給你 k , l ， k 為貪心演算法與正確解答的差距， l 為最少要生成數列的長度，請您給出一組數列能夠在正確的演算法成功輸出正確答案，也能讓貪心演算法與正確演算法的差距等於 k，如果不行請輸出 -1

分析

這種解題方式我還是第一次看到阿，只能說自己見識太淺還需要磨練

這題我是直接去看別人 BLOG 分析的 CODE 才 AC 的，但是他沒有解析，我在這邊附註解析好讓未來的自己複習，會在後面附上連結。

這題分成幾個步驟:

由於題目有限制數列長度必小於 2000，於是我們直接把每一個生成的陣列都直接定義成 1999，就可以直接輕鬆跳過 l 的問題。

長度必小於 2000

根據貪心演算法的程式碼，當 \(curMAX < 0 \) 時，我們就直接捨棄掉，只用後面的 \( left \)，於是我們可以用一個簡單方法直接找出貪心演算法的最大問題核心。

舉例說明

EX: 舉例數列為 -1 1 1 3

演算法	數列總和	長度	總和*長度=答案
貪心演算法	5	3	\( 5 \cdot 3 = 15\)
正確演算法	4	4	\( 4 \cdot 4 = 16 \)

看出來了嗎?
問題在於如果一開始為 -1 時貪心演算法永遠都會捨棄那長度，於是我們只要設計出一個數列是可以破解他的貪心演算法就完成了。

怎麼破解?

其實我們也不用那麼麻煩一定要讓自己想出一個絕對正確的演算法，我們只要將貪心演算法稍加改良在讓我們產生的數列可以產生出一個差額為 k 值，是不是非常聰明！教導我的 BLOG 就是這樣做的，真的優秀

設計演算法

根據舉例，我們可以得出一結論

1. 貪心演算法的長度永遠會比正確演算法少 1
2. 正確演算法的長度永遠會比貪心演算法多 1

根據數學乘法公式，可找出適合的 k 值，這裡我們用舉例的方式來說明比較清楚:

EX:1 前項為數列總和(定義為 A) 後項為長度總和(定義為 B)

數列: -1 1 1 3
\(5 \cdot 3 = 15 \)
\(4 \cdot 4 = 16 \)
\(16 - 15 = 1 , k = 1 \)

EX:2 前項為數列總和(定義為 A) 後項為長度總和(定義為 B)

數列: -1 1 1 4
\(6 \cdot 3 = 18 \)
\(5 \cdot 4 = 20 \)
\(20 - 18 = 2 , k = 2 \)

證明

當 \(C \cdot D = E \) 時，如果 C 項 -1，則 E - D (定義為 F)

\(7 \cdot 2 = 14\)
\(6 \cdot 3 = 18\)
\(18 - 14 = 4 , k = 4 \)
經過轉變後
\(7 \cdot 3 = 21 \)
\(6 \cdot 3 = 18 \)
在將 \(7 \cdot 3 = 21 \) 的 3 -1 ，於是 \(21 - 18 -7 = -4\)得此證明 k。

證明好了，那我應該怎麼做?

由於數列中的數字的大小必小於 2000，理所當然的 k 最大只能到 1999，所以我們可以用透過放大中間的數列來讓 k 值加大

EX:3

數列: -1 2 2 3
\(7 \cdot 3 = 21 \)
\(6 \cdot 4 = 24 \)
\(24 - 21 = 3 , k = 3 \)
由於中間的數值從 1 被我放大到 2，所以 k 的值也隨之 +2，原因是因為中間的數列長度為 2 且原本的 1 都被我在 +1 ，於是 \(1 * 2 = 2\)

結論

當雙方 A 都增加 1，且雙方 B 一樣都不變時， k 的值會 +1，並且當 k 必須大於 2000 時我們必須放大中間數列，OK 我們找到公式了！

找到公式了，但在等等題目很壞心眼

由於題目很惡意，他 l 的範圍並不是在 \(0 \leq l < 2000\)，是在 \(0 \leq < 10^{9}\)，於是你必須多加行 if 判斷如果 \(l \geq 2000\) 就 cout -1 ，OK開始寫 code 吧

心得

這題對於不擅長數論的我來說非常痛苦阿，前面的證明我也並不覺得我證明得很好，如果我的文字敘述上有錯誤，拜託跟我講QQQQQQ，或是有更好的表達方式請告訴我，我會改進。
這題我光看懂大神的程式碼就花了 3hr，自己的領悟力還是不夠強還需要努力，也是第一次遇到這種需要設計題目的，學起來了！

附上我從大神學來知識的 BLOG
打了篇文章也花了我 2hr 整，自己的表達能力需要加強，寫 BLOG 也不是一件簡單的事情啊…

#include <bits/stdc++.h>
#define MAXN 2020
#define LOCAL
using namespace std ;
int arr[MAXN] = {} ;

int main(){
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    int t , k , l ;
    cin >> t ;
    while(t--){
        cin >> k >> l ;
        arr[1] = -1 ;
        if(l >= 2000){
            cout << -1 << '\n' ;
            continue ;
        }

        fill(arr+2 , arr+2000 , (1999 + k) / 1998) ;
        arr[1999] += (1999 + k ) % 1998 ;

        cout << 1999 << '\n' ;
        for(int i = 1 ; i <= 1999 ; i++){
            cout << arr[i] << ' ' ;
        }
        cout << '\n' ;
    }
}