題目1

題目鏈接
題目大意：
在一個(gè)國(guó)際象棋的棋盤(pán)上绊含，有一個(gè)棋子，它的移動(dòng)規(guī)則類(lèi)似馬炊汹，能夠朝著橫or豎方向移動(dòng)距離a躬充，然后朝豎or橫（和之前不同）移動(dòng)距離b；
比如說(shuō)馬的移動(dòng)規(guī)則就是a=1讨便，b=2充甚；

現(xiàn)在棋盤(pán)上還有另外兩個(gè)棋子K和Q，問(wèn)棋盤(pán)上有多少個(gè)特殊位置霸褒，在該位置上面可以移動(dòng)棋子K所在位置伴找，也可以移動(dòng)到棋子Q所在位置。

如下废菱，該圖上面的馬技矮，可以移動(dòng)到另外兩個(gè)棋子的位置。

輸入：
第一行殊轴，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤1000)
每個(gè)樣例3行
第1行整數(shù) ?? and ?? (1≤??,??≤1e8)
第2行整數(shù) ???? and ???? (0≤????,????≤1e8 )
第3行整數(shù) ???? and ???? (0≤????,????≤1e8 )

輸出：
每個(gè)樣例一行衰倦，輸出滿(mǎn)足要求的位置數(shù)量。

Examples
input
4
2 1
0 0
3 3
1 1
3 1
1 3
4 4
0 0
8 0
4 2
1 4
3 4

output
2
1
2
0

題目解析：
能夠攻擊到k的位置梳凛，應(yīng)該有左右上下8個(gè)角落耿币；
同理，能夠攻擊到q的位置韧拒，也同樣有8個(gè)角落淹接；
接下來(lái)枚舉前面的位置，看是否有位置與后面的角落重合叛溢，即可塑悼。

tips：
1、為了方便枚舉楷掉，可以把4個(gè)方向用dir[4][2]的數(shù)組來(lái)枚舉厢蒜；
2、a和b不相同的時(shí)候，要考慮a和b互換的情況斑鸦；

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    int dir[4][2] = {1,1,  -1,1,  1,-1,   -1,-1};
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int val[2], x1, y1, x2, y2;
            cin >> val[0] >> val[1];
            cin >> x1 >> y1;
            cin >> x2 >> y2;
            int ans = 0;
            for (int i = 0; i < 8; ++i) {
                int a = val[i % 2];
                int b = val[(i + 1) % 2];
                if (a == b && i % 2) continue;;
                int idx1 = dir[i/2][0] * a + x1;
                int idy1 = dir[i/2][1] * b + y1;
                for (int j = 0; j < 8; ++j) {
                    int a2 = val[j % 2];
                    int b2 = val[(j + 1) % 2];
                    if (a2 == b2 && j % 2) continue;;
                    if ((idx1 + dir[j/2][0] * a2 == x2) && (idy1 + dir[j/2][1] * b2 == y2)) {
                        ++ans;
                        break;
                    }
                }
            }
            cout << ans << endl;
        }
    }
}
ac;

題目2

題目鏈接
題目大意：
有n個(gè)元素的整數(shù)數(shù)組a愕贡，現(xiàn)在進(jìn)行以下操作：
1、選擇某個(gè)元素a[i]巷屿，移除當(dāng)前元素a[i]固以，獲得初始分?jǐn)?shù)score=a[i]；
2嘱巾、尋找某個(gè)元素a[j]憨琳，并且滿(mǎn)足score>=a[j]，可以移除元素a[j]旬昭，同時(shí)使得分?jǐn)?shù)score增加a[j]篙螟；
3、不斷重復(fù)操作2问拘，直到無(wú)法執(zhí)行遍略；

現(xiàn)在想知道，每個(gè)元素被作為初始元素時(shí)场梆，最多能夠移除的元素?cái)?shù)量墅冷；

輸入：
第一行纯路，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤5000)
每個(gè)樣例2行
第1行整數(shù) ?? (1≤??≤1e5 )
第2行n個(gè)整數(shù) ??1,??2,…,???? (1≤????≤1e9)

輸出：
每個(gè)樣例一行或油，每行n個(gè)整數(shù)，第i個(gè)數(shù)字驰唬，表示當(dāng)?shù)趇個(gè)元素作為初始元素時(shí)顶岸，能夠移除的最多元素?cái)?shù)量。（也就是操作2的最多執(zhí)行次數(shù)）

Examples
input
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000

output
4 3 0 3 1
1 0 2
0
4 4 4 4 4

題目解析：
將整數(shù)數(shù)組進(jìn)行從大到小排序叫编，接著下來(lái)再考慮如何決策辖佣；
由于題目的規(guī)則很像“大魚(yú)吃小魚(yú)”，可以從數(shù)字較小者開(kāi)始搓逾，也就是從右到左：
1卷谈、最小的元素，除非和倒數(shù)第二個(gè)相同霞篡，否則無(wú)法吃下任何數(shù)字世蔗；
2、從倒數(shù)第二個(gè)數(shù)字開(kāi)始朗兵，每次可以直接累加右邊所有的數(shù)字污淋，然后如果數(shù)字和大于等于左邊的數(shù)字，就可以一直累加余掖，然后左移一位寸爆，直到無(wú)法移動(dòng)；
此時(shí)，該段區(qū)間內(nèi)的所有數(shù)字赁豆，最終的數(shù)字和都是一樣的仅醇；
3、重復(fù)上面的過(guò)程魔种，直到將整個(gè)數(shù)組分為若干段着憨；
比如說(shuō)[20, 5,4,2,1]就可以分為[20],[5,4], [2], [1]，劃分規(guī)則就是每次從右到左累加和务嫡，小于左邊一個(gè)數(shù)字甲抖。

類(lèi)似的思考過(guò)程，假設(shè)我們排序之后是從左到右去思考心铃，還是以[20, 5,4,2,1]為例子准谚。
當(dāng)處理數(shù)字20時(shí)，按照規(guī)則去扣，右邊所有數(shù)字都能吃掉柱衔，ans[0]=4；
當(dāng)處理數(shù)字5時(shí)愉棱，如果5左邊所有數(shù)字累加和大于20唆铐，那么就可以吃掉20，此時(shí)結(jié)果ans[1]=ans[0]; 但是5左邊累加數(shù)字和奔滑，結(jié)果是12艾岂，那么此時(shí)結(jié)果就是3；
因?yàn)閿?shù)組比較長(zhǎng)朋其，右邊和可以先計(jì)算整個(gè)數(shù)組和sum王浴，然后不斷累積減去當(dāng)前數(shù)字。

typedef long long lld;
 
class Solution {
    static const int N = 101010;
    pair<int, int> a[N];
    int ans[N];
    static bool cmp(pair<int, int> x, pair<int, int> y) {
        return x.first > y.first;
    }
    
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            lld sum = 0;
            for (int i = 0; i < n; ++i) {
                cin >> a[i].first;
                a[i].second = i;
                sum += a[i].first;
            }
            sort(a, a + n, cmp);
            for (int i = 0; i < n; ++i) {
                sum -= a[i].first;
                if (i == 0) {
                    ans[a[i].second] = n - i - 1;
                }
                else {
                    if (sum + a[i].first >= a[i - 1].first) {
                        ans[a[i].second] = ans[a[i - 1].second];
                    }
                    else {
                        ans[a[i].second] = n - i - 1;
                    }
                }
            }
            for (int i = 0; i < n; ++i) cout << ans[i] << " ";
            cout << endl;
        }
    }
}
ac;

題目3

題目鏈接
題目大意：
有n個(gè)整數(shù)的數(shù)組a梅猿，現(xiàn)在可以進(jìn)行下面的操作：
選擇數(shù)組中任意兩個(gè)元素氓辣，將兩個(gè)元素差值的絕對(duì)值，插入到數(shù)組中的最后面袱蚓；

現(xiàn)在可以進(jìn)行上面的操作k次钞啸，要求讓數(shù)組中的最小值在操作之后，盡可能的欣恕体斩；

輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤1000)
每個(gè)樣例2行
第1行整數(shù)?? and ?? (2≤??≤2?1e3 , 1≤??≤1e9 )
第2行n個(gè)整數(shù) ??1,??2,…,???? (1≤????≤1e18)

輸出：
每個(gè)樣例一行响蓉，輸出操作后的最小值硕勿。

Examples
input
4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000

output
1
0
3
500000000000000000

題目解析：
數(shù)組a都是大于1的值，那么最終的結(jié)果必然是大于等于0枫甲；
當(dāng)n=2的時(shí)候源武，如果a1=a2扼褪，那么結(jié)果就是0；
如果a1!=a2粱栖，那么|a1-a2|必然會(huì)產(chǎn)生一個(gè)新的數(shù)字话浇，以[4, 2]為例：
4 2
4 2 2
4 2 2 0

但是，當(dāng)a1和a2差距較大時(shí)闹究，我們有：
10 2
10 2 8
10 2 8 2
10 2 8 2 0

也就是當(dāng)操作次數(shù)沒(méi)有限制時(shí)彤钟，我們必然能夠產(chǎn)生0猩系，比如說(shuō)：
c=b-a；
d=b-c=(b-(b-a))=a;
這樣數(shù)組[a, b, c, d]，只需要選擇a-d=a-a=0休蟹；
只要k>=3幕侠，必然可以得到0油挥。

當(dāng)k==1時(shí)顾患，直接枚舉兩兩想減的情況，得到結(jié)果用踩；
當(dāng)k==2時(shí)渠退，我們枚舉數(shù)組兩兩想減，得到新的數(shù)字脐彩，假設(shè)是數(shù)組b碎乃；
這樣我們就有[a1, a2, a3... an] 和 [b1, b2, b3...bn]兩個(gè)數(shù)組；
這樣只需要再枚舉數(shù)組a和數(shù)組b相減惠奸，得到數(shù)組c梅誓；
最小值就是數(shù)組a、b晨川、c中的最小值证九。

這樣的復(fù)雜度删豺，首先是數(shù)組b的生成共虑，O(N^2)，最多會(huì)生成1e6個(gè)數(shù)字呀页；
最后再枚舉生成c的時(shí)候妈拌，復(fù)雜度就達(dá)到了O(N^3），最終復(fù)雜度超標(biāo)蓬蝶。

重新審視問(wèn)題分析過(guò)程尘分，當(dāng)k==1時(shí)，其實(shí)不需要所有數(shù)字兩兩相減丸氛，舉一個(gè)例子：
當(dāng)數(shù)組為[9,7,5,1]培愁，當(dāng)枚舉9與其他數(shù)字的差值時(shí)，只需要考慮[9,7]的情況缓窜，也就是整個(gè)數(shù)組其實(shí)只需要考慮3個(gè)情況[9, 7] 定续、[7,5]谍咆、[5,1]；
這里的前提私股，是數(shù)組是有序的摹察。可以對(duì)數(shù)組進(jìn)行排序倡鲸，復(fù)雜度是O(NlogN）供嚎，接下來(lái)枚舉復(fù)雜度就是O(N）；
但是峭状，當(dāng)k==2時(shí)克滴，是否可以繼續(xù)只考慮相鄰數(shù)字呢？
是不可以的优床，因?yàn)橄噜彅?shù)字想減偿曙，生成的只是當(dāng)前最小，不意味著再一次操作的更小羔巢，比如說(shuō)[9,7,5,4]望忆，第一次無(wú)法生成9-5=4，那么第二次操作就無(wú)法歸零竿秆。
所以首次操作启摄，需要生成N^2個(gè)數(shù)字的數(shù)字b；
在第二次操作的時(shí)候幽钢，我們會(huì)從數(shù)組a選擇1個(gè)數(shù)字歉备，再?gòu)臄?shù)組b選擇1個(gè)數(shù)字，此時(shí)可以參考k=1的時(shí)候的做法匪燕，將數(shù)組b排序蕾羊，對(duì)于每個(gè)數(shù)字a[i]，我們只需要考慮數(shù)組b中離a[i]數(shù)字最接近的數(shù)字帽驯。
此時(shí)可以用二分法龟再，在數(shù)組b中尋找。但是我們有更簡(jiǎn)單的做法：
將數(shù)組a和數(shù)組b一起排序尼变，然后對(duì)于a[i]利凑，我們就往左右遍歷，這樣就能更方便去找到數(shù)字嫌术。

typedef long long lld;

class Solution {
   static const int N = 4010100;
   lld a[N];
   pair<lld, lld> b[N];
   
public:
   void solve() {
       int t;
       cin >> t;
       while (t--) {
           int n, k;
           cin >> n >> k;
           
           for (int i = 0; i < n; ++i) cin >> a[i];
           sort(a, a + n);
           
           if (k >= 3) {
               cout << 0 << endl;
           }
           else if (k == 2) {
               int cnt = 0;
               for (int i = 0; i < n; ++i) {
                   b[cnt].first = a[i];
                   b[cnt].second = 0;
                   cnt++;
               }
               
               for (int i = 0; i < n; ++i) {
                   for (int j = i + 1; j < n; ++j) {
                       b[cnt].first = abs(a[i] - a[j]);
                       b[cnt].second = 1;
                       ++cnt;
                   }
               }
               
               sort(b, b + cnt);
               
               lld ans = a[0];
               for (int i = 0; i < cnt; ++i) {
                   ans = min(ans, b[i].first);
                   if (b[i].second == 0) { // 數(shù)組a來(lái)匹配最近的一個(gè)數(shù)字
                       int x = i, y = i;
                       while (x > 0) {
                           --x;
                           if (b[x].second == 1) break;
                       }
                       
                       while (y < cnt - 1) {
                           ++y;
                           if (b[y].second == 1) break;
                       }
                       if (x != i) {
                           ans = min(ans, abs(b[i].first - b[x].first));
                       }
                       if (y != i) {
                           ans = min(ans, abs(b[i].first - b[y].first));
                       }
                   }
               }
               
               cout << ans << endl;
           }
           else if (k == 1) {
               lld ans = a[0];
               for (int i = 1; i < n; ++i) ans = min(ans, min(a[i], a[i] - a[i - 1]));
               cout << ans << endl;
           }
       }
   }
}
ac;

題目4

題目鏈接
題目大意：
給出n個(gè)整數(shù)的數(shù)組a和b哀澈，現(xiàn)在可以對(duì)數(shù)組a進(jìn)行操作：
選擇數(shù)組內(nèi)任意區(qū)間[l, r]，將區(qū)間[l, r]內(nèi)的整數(shù)都改為區(qū)間的最大值度气。
比如割按，對(duì)于數(shù)組[1, 2, 3, 4, 5]，選擇區(qū)間[1, 3]進(jìn)行操作磷籍，則會(huì)生成[3, 3, 3, 4, 5]适荣；

現(xiàn)在想知道丙躏，數(shù)組a是否可以進(jìn)行若干次上面的操作，最終變成數(shù)組b束凑。

輸入：
第一行晒旅，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤10000)
每個(gè)樣例3行
第1行整數(shù) n (1≤n≤1000)
第2行整數(shù) ??1,??2,…,???? (1≤????≤??)
第3行整數(shù) ??1,??2,…,???? (1≤????≤??)

輸出：
每個(gè)樣例一行，如果可行則輸出YES汪诉，如果不可行則輸出NO废恋；

Examples
input
5
5
1 2 3 2 4
1 3 3 2 4
5
3 4 2 2 4
3 4 3 4 4
5
3 2 1 1 1
3 3 3 2 2
2
1 1
1 2
3
1 1 2
2 1 2

output
YES
NO
YES
NO
NO

題目解析：
從數(shù)據(jù)量較小的情況開(kāi)始分析，比如說(shuō)n=2時(shí)扒寄，數(shù)組數(shù)字可以簡(jiǎn)化成1和2鱼鼓；
那么就會(huì)有[1,2]和[2,2]，比較容易得到結(jié)果该编；
當(dāng)n=3時(shí)迄本，我們?cè)黾觽€(gè)數(shù)組3，如果放在數(shù)組[1,2]左右兩邊课竣，對(duì)結(jié)果不影響嘉赎；但是如果放在中間，數(shù)組[1, 3, 2]是無(wú)法變成[2, 3, 2]于樟；
由此我們可以知道公条，較大的數(shù)字會(huì)阻斷較小的數(shù)字傳遞；
當(dāng)n=4時(shí)迂曲，我們可以看到一個(gè)有意思的樣例：
1,2,3,4
3,4,4,4
數(shù)字3靶橱，跨過(guò)第2個(gè)數(shù)字影響到了第1個(gè)數(shù)字，然后第2路捧、3個(gè)數(shù)字最終又被數(shù)字4覆蓋关霸。
由此我們可以知道，數(shù)字的影響是最終可能非間隔杰扫，但是必須傳遞過(guò)去队寇，并且中間路徑可能被更大數(shù)字覆蓋。

至此涉波，我們的思路就清晰起來(lái)：
1英上、從小到大來(lái)枚舉數(shù)字，因?yàn)楫?dāng)x覆蓋過(guò)某個(gè)數(shù)字后啤覆，只有x+1才能覆蓋這個(gè)覆蓋；
2惭聂、每一個(gè)數(shù)字窗声，都可以向左右蔓延，蔓延條件有兩個(gè)辜纲，隔壁數(shù)字小于等于當(dāng)前數(shù)字笨觅，隔壁數(shù)字對(duì)應(yīng)的數(shù)組b元素要大于等于當(dāng)前數(shù)字拦耐；
3、重復(fù)上面所有的過(guò)程见剩，直到所有數(shù)字結(jié)束杀糯；

這里的核心依據(jù)，就是通過(guò)數(shù)組b的元素作為數(shù)組a元素的上限苍苞，盡可能讓每一個(gè)數(shù)組a元素去變大固翰。

思考：
當(dāng)N的范圍再擴(kuò)大1000倍呢？上面的這個(gè)做法在效率上就會(huì)不足羹呵，但是思路可以沿用擴(kuò)展骂际。
首先回顧這里的耗時(shí)操作，首先是枚舉數(shù)字從小到大冈欢，然后找到和這個(gè)位置對(duì)應(yīng)的數(shù)字歉铝，簡(jiǎn)單實(shí)現(xiàn)是O（N^2）的復(fù)雜度，但是我們先預(yù)處理一遍數(shù)組凑耻，記錄每個(gè)數(shù)字對(duì)應(yīng)的下標(biāo)太示，這樣就可以做到O（N）的復(fù)雜度；
其次是在數(shù)字覆蓋的過(guò)程中香浩，有時(shí)會(huì)出現(xiàn)每個(gè)位置被重復(fù)覆蓋多次的情況先匪，但是對(duì)于結(jié)果而言，我們只需要知道某個(gè)位置不匹配時(shí)（a[i] != b[i]）弃衍，它應(yīng)該往數(shù)組a左邊/右邊去找到等于b[i]的元素呀非。
這個(gè)過(guò)程，同樣可以預(yù)處理镜盯。
比如說(shuō)對(duì)于下面的樣例岸裙，當(dāng)a[3] != b[3]，我們要往數(shù)組a兩邊去找數(shù)組元素等于3的情況速缆；
3 3 2 1 4 3 3
3 3 3 3 4 3 3
首先在前面的預(yù)處理步驟降允，我們記錄每一個(gè)數(shù)字的位置，那么對(duì)于數(shù)字3艺糜，我們同樣記錄了3在數(shù)組a的位置為[0,1,5,6]剧董，這樣我們很容易知道對(duì)于a[3]而言，最近數(shù)字3位置在a[1]和a[5]破停；

接下來(lái)的問(wèn)題是翅楼，對(duì)于某個(gè)位置i和某個(gè)位置j，是否能夠匹配真慢？
還是用上面的樣例毅臊，我們才用采樣這樣的策略：
1、對(duì)于數(shù)組a黑界，我們從小到大枚舉的元素的過(guò)程管嬉，我們把枚舉過(guò)的數(shù)字（包括當(dāng)前數(shù)字）皂林，在數(shù)組a出現(xiàn)的位置都用1來(lái)標(biāo)明；（某個(gè)位置為1蚯撩，表示該位置可以延伸）
2础倍、對(duì)于數(shù)組b，我們從小到大枚舉的元素的過(guò)程胎挎，我們把還沒(méi)有枚舉過(guò)的數(shù)字（包括當(dāng)前數(shù)字）沟启，在數(shù)組b出現(xiàn)的位置都用1來(lái)標(biāo)明；（某個(gè)位置為1呀癣，表示該位置可以延伸）
樣例數(shù)據(jù)
3 3 2 1 4 3 3
3 3 3 3 4 3 3
就可以轉(zhuǎn)義為
1 1 1 1 0 1 1
1 1 1 1 1 1 1
這樣美浦， 當(dāng)我們?cè)谂袛郺[1]和a[3]是否能夠匹配時(shí)，其實(shí)就是判斷數(shù)組a區(qū)間[1, 3]的數(shù)字和是否為3项栏，并且數(shù)組b區(qū)間[1,3]的數(shù)字和是否為3浦辨；

那么如何做快速的標(biāo)記、以及計(jì)算累加和呢沼沈？
1流酬、標(biāo)記問(wèn)題，通過(guò)預(yù)處理我們能O(1)獲取對(duì)應(yīng)位置列另，并且每個(gè)數(shù)字我們只會(huì)標(biāo)記一次芽腾，所以總的標(biāo)記復(fù)雜度是O(N)；
2页衙、計(jì)算累加和摊滔，在一個(gè)數(shù)組里面，可以對(duì)某些元素進(jìn)行數(shù)值修改店乐、然后要求區(qū)間和艰躺，可以用線(xiàn)段樹(shù)來(lái)解決。

class Solution {
    static const int N = 201010;
    int a[N], b[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; ++i) cin >> a[i];
            for (int i = 0; i < n; ++i) cin >> b[i];
            for (int k = 1; k <= n; ++k) {
                for (int i = 0; i < n; ++i) {
                    if (a[i] == k) {
                        int x = i - 1, y = i + 1;
                        while (x >= 0 && a[x] <= k && k <= b[x]) {
                            a[x] = k;
                            --x;
                        }
                        while (y < n && a[y] <= k && k <= b[y]) {
                            a[y] = k;
                            ++y;
                        }
                    }
                }
            }
            int ans = 1;
            for (int i = 0; i < n; ++i) ans = ans && (a[i] == b[i]);
            cout << (ans ? "YES" : "NO") << endl;
        }
    }
}
ac;

題目5

題目鏈接
題目大意：
有n個(gè)正整數(shù)的數(shù)組a眨八，現(xiàn)在Alice和Bob在玩游戲腺兴，Alice先操作，Bob再操作廉侧；
Alice會(huì)移除數(shù)組中页响，最多k個(gè)元素；
Bob會(huì)將數(shù)組中段誊，最多x個(gè)元素乘以-1闰蚕；

每個(gè)人只行動(dòng)一次，Alice想要讓最終數(shù)組的元素和盡可能大枕扫，Bob想要讓數(shù)組的元素和盡可能信汶纭；
問(wèn)最終的數(shù)字和為多少烟瞧；

輸入：
第一行诗鸭，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤10000)
每個(gè)樣例2行
第一行，整數(shù)?? , ?? , and ?? (1≤??≤2?1e5 , 1≤??,??≤?? )
第二行参滴，n個(gè)整數(shù)??1,??2,…,???? (1≤????≤1000)

輸出：
每個(gè)樣例一行强岸，輸出最終的數(shù)字和；

Examples
input
8
1 1 1
1
4 1 1
3 1 2 4
6 6 3
1 4 3 2 5 6
6 6 1
3 7 3 3 32 15
8 5 3
5 5 3 3 3 2 9 9
10 6 4
1 8 2 9 3 3 4 5 3 200
2 2 1
4 3
2 1 2
1 3

output
0
2
0
3
-5
-9
0
-1

題目解析：
由于題目有k和x兩個(gè)變量砾赔，我們先考慮x=1個(gè)數(shù)字的情況蝌箍；
假設(shè)題目數(shù)據(jù)已經(jīng)從大到小排序，數(shù)組還是a暴心，以4妓盲、3、2专普、1為例悯衬；
先考慮bob的操作（為什么是先考慮后手？因?yàn)檫@樣思考簡(jiǎn)單）
假設(shè)Alice沒(méi)有操作檀夹，那bob一定會(huì)選擇-4筋粗，也就是數(shù)組最大的元素；（如果x=2炸渡，那么就是前2個(gè)）

那么Alice如果操作呢娜亿？
移除4的好處是最終消除了-4，但是增加了-3蚌堵，同時(shí)移除原來(lái)正數(shù)3买决，總體的代價(jià)應(yīng)該是4-3-3=-2，所以Alice不操作結(jié)果更佳吼畏；

由此可知道數(shù)組排序后督赤，Alice如果移除，一定是移除前面若干個(gè)數(shù)字宫仗；Bob的負(fù)數(shù)操作够挂，也一定是前面x個(gè)數(shù)字。
那么只需要枚舉下k=0藕夫、1孽糖、2、3毅贮、办悟、、k的情況滩褥，對(duì)應(yīng)的結(jié)果病蛉。（邊界情況比較容易些錯(cuò)，可以直接模擬，簡(jiǎn)化過(guò)程）

注意：
一些特殊case
k=2, x=2
4+3+2+1
-4-3+2+1=-4
-3-2+1=-4
-2-1=-3

k=2, x=2
6+6+3.5+1
-6-6-+4.5=-7.5
-3.5-1=-4.5

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    lld a[N], sum[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k, x;
            cin >> n >> k >> x;
            for (int i = 0; i < n; ++i) cin >> a[i];
            sort(a, a + n, greater<int>());
            sum[0] = a[0];
            // [left, mid, right]
            // left是移除铺然，mid是負(fù)數(shù)俗孝，right是剩下
            lld leftSum = 0, midSum = 0, rightSum = 0;
            for (int i = 0; i < x; ++i) midSum += a[i];
            for (int i = x; i < n; ++i) rightSum += a[i];
            lld ans = rightSum - midSum;
            for (int remove = 1; remove <= k; ++remove) {
                midSum -= a[remove - 1]; //移除當(dāng)前這個(gè)數(shù)字
                if (remove + x <= n) {
                    // 右邊還有剩余
                    midSum += a[remove + x - 1]; // midSum增加這個(gè)數(shù)字
                    rightSum -= a[remove + x - 1]; // rightSum移除這個(gè)數(shù)字
                }
                ans = max(ans, rightSum - midSum);
            }
            cout << ans << endl;
        }
    }
}
ac;