將所有的商店按照「從?到?」的順序「排序」，把貨倉建在中位數處，可以使得貨倉到每家商店的距離之和最?：

• 如果n是奇數，貨倉建在a[(n + 1)/2] 位置處；
• 如果n是偶數，貨倉建在a[n/2] ～ a[n/2 + 1]之間都是可以的

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e5+10;int n;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a+1, a+1+n);LL ret = 0;for (int i = 1; i <= n; i++){//中間位置的下標是(1+n)/2ret += abs(a[i] - a[(1+n) / 2]);}cout << ret << endl;return 0;
}

$$|a?x|+|b?x|\ge |a?b|$$

當x處于兩者的中間位置時，左式取得最小值
形如：
$$sum=\sum _{i=1}^n|a[i]?x|=|a[1]?x|+|a[2]?x|+?+|a[n]?x|$$

• 當x 取到n 個數的中位數時，和最?；
• 最?和為：
  $$(a[n]?a[1])+(a[n?1]?a[2])+...+(a[n+1?n/2]?a[n/2])$$

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e5+10;int n;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a+1, a+1+n);LL ret = 0;for (int i = 1; i <= n/2; i++){ret += abs(a[i] - a[n+1-i]);      }cout << ret << endl;return 0;
}

貪?想法：從前往后累加，我們會遇到下?兩種情況：

• ?前的累加和>=0：那么當前累加和還會對后續的累加和做出貢獻，那我們就繼續向后累加，然后更新結果；
• ?前的累加和<0：對后續的累加和做不了?點貢獻，直接?膽舍棄計算過的這?段，把累加和重置為0，然后繼續向后累加。
  這樣我們在掃描整個數組?遍之后，就能更新出最??段和。
  

在累加的過程中算出?段區間和sum[a,b]<0 ，如果不舍棄這?段，那么[a,b]段之間就會存在?點，「以某個位置為起點」就會「更優」，分為下?兩種情況

1. 在ab段存在?個點c ，從這個位置開始，「越過b 」的累加和?從a 開始的累加和更優：
   ?「反證法」證明這種情況不存在。
   如果存在這?點，那么：sum[c, b] > sum[a, b] ，這樣才能保證向后加的時候更優。
   但這是「不可能」的。如果sum[c, b] > sum[a, b] ，那么sum[a, c-1]<0，這與我們的貪?策略?盾。
   因為我們貪?策略向后加的時候，只要不?于0，就會?直加下去。如果[a, c-1]段?于0，就
   會在c點之前停?，不會累加到b。
   因此區間內不存在?點，在計算?數組和時，在「越過b 」的情況下，能?從a 開始更優。
2. 在ab段存在?個點c ，從這個位置開始，「不越過b 」的累加和?從a 開始的累加和更優：
   也可以?「反證法」證明這種情況不存在。
   如果存在這?點，那么：sum[c, k] > sum[a, k] 。
   但這是不可能的。如果sum[c, k] > sum[a, k]，那么sum[a, c - 1] < 0 ，這與我們的貪?策略?盾。
   因此區間內不存在?點，在計算?數組和時，在「不越過b 」的情況下，能?從a 開始更優。
   綜上所述，我們可以?膽舍棄這?段，重新開始。

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;typedef long long LL;int n;
LL a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];LL sum = 0, ret = -1e6;for (int i = 1; i <= n; i++){sum += a[i];ret = max(ret, sum);if (sum < 0) sum = 0;}cout << ret << endl;return 0;
}

先將所有的紀念品排序，每次拿出當前的最?值x 與最?值y ：

• 如果x + y ≤ w ：就把這兩個放在?起；
• 如果x + y > w：說明此時最?的和誰都湊不到?起，y單獨分組，x繼續留下在進?下?次判斷。
  直到所有的物品都按照上述規則分配之后，得到的組數就是最優解

可以?「交換論證法」證明貪?解就是最優解：
對于區間[ai......aj]，如果存在最優解，但是ai與aj的分配?式與我們貪?解的分配?式不?樣，那么就會有以下?種情況：

1. 當a[i] + a[j] > w時：

• 貪?解會把a[j]單獨分組，a[i]留待下次考慮；
• 最優解也必定會把a[j]單獨分組，因為沒有更?的值與a[j]組合。
  此時貪?解與最優解?致。

2. 當a[i] + a[j] ≤ w時：

• 貪?解會把兩者組合分在?個組??；
• 最優解可能有以下?種情況：
  • a[j]單獨?組：
    • 如果a[i]也單獨?組的話，最優解還不如貪?解分的組少，?盾；
    • 如果a[i]和另?個a[k]?組的話，我們可以把a[k]與a[j]交換，此時并不影響結果，和貪?解?致。
  • a[j]和a[k]?組：
    • 如果a[i]單獨?組的話，交換a[i]和a[k]，此時并不影響最終結果，和貪?解?致；
    • 如果a[i]和a[l]?組的話，交換a[i]和a[k]，此時變成(a[i]+a[j]),(a[l]+a[k])，其中a[l]+a[k]<=a[j]+a[k]<=w，不影響最終結果，和貪?解?致。
      綜上所述，我們可以通過不斷的「調整」，使的最優解在「不改變其最優性」的前提下，變得和貪?解?致。那我們的貪?策略就等價于最優策略。

#include <bits/stdc++.h>
using namespace std;const int N = 3e4 + 10;int w, n;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> w >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a+1, a+1+n);int l = 1, r = n, ret = 0;while (l <= r){if(a[l] + a[r] <= w) l++, r--;else r--;ret++;}cout << ret << endl;return 0;
}

由題意可得，我們會發現?些性質：

• 設置橫向通道的時候，并「不影響」左右相鄰的同學；
• 設置縱向通道的時候，并「不影響」上下相鄰的同學。
  因此我們可以「分開」處理橫向通道和縱向通道。
  處理橫向通道（縱向同理，就不多贅述）：
• 收集每??如果放上通道之后，會解決多少個交頭接?的同學；
• 對收集的信息「從?到?」排序，選最?的k ?就是最優結果。

#include <bits/stdc++.h>
using namespace std;const int N = 1010;struct node
{int index;int cnt;
}row[N], col[N];int m, n, k, l, d;//按cnt從大到小
bool cmp1(node& x, node& y)
{return x.cnt > y.cnt;
}
//按index從小到大
bool cmp2(node& x, node& y)
{return x.index < y.index;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> m >> n >> k >> l >> d;//初始化結構體數組for (int i = 1; i <= m; i++) row[i].index = i;for (int i = 1; i <= n; i++) col[i].index = i;while(d--){int x, y, p, q; cin >> x >> y >> p >> q;if (x == p) col[min(y, q)].cnt++;else row[min(x, p)].cnt++;}//對兩個數組按照cnt從大到小排序sort(row+1, row+1+m, cmp1);sort(col+1, col+1+n, cmp1);//對row數組，前k個元素，按照下標從小到大排序sort(row+1, row+1+k, cmp2);//對col數組，前l個元素，按照下標從小到大排序sort(col+1, col+1+l, cmp2);for (int i = 1; i <= k; i++){cout << row[i].index << " ";}cout << endl;for (int i = 1; i <= l; i++){cout << col[i].index << " ";}cout << endl;return 0;
}

最優解是先暴?枚舉所有?的選法，在?的選擇都確定之后，再去貪?的處理列

#include <bits/stdc++.h>
using namespace std;const int N = 20;int n, m, k;
int a[N][N];
int col[N]; //統計列和//統計x的二進制中1的個數
int calc(int x)
{int ret = 0;while (x){ret++;x -= x & -x;}return ret;
}//從大到小排序
bool cmp(int a, int b)
{return a > b;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m >> k;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> a[i][j];int ret = 0;//暴力枚舉行所有選法for (int st = 0; st < (1 << n); st++){int cnt = calc(st);if (cnt > k) continue; //不合法memset(col, 0, sizeof col);int sum = 0; //記錄當前選法的和for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if ((st >> i) & 1) sum += a[i][j];else col[j] += a[i][j];}}//處理列sort(col, col + m, cmp);//選k - cnt列for (int j = 0; j < min(k - cnt, m); j++) sum += col[j];ret = max(ret, sum);}cout << ret << endl;return 0;
}