時間限制：2s
內存限制：512MB
【題目描述】
申徒嘉和鄭子產都是伯昏無人的學生，子產因為申徒嘉是殘疾人，非常看不起他，于是
想要刁難他。
子產給了申徒嘉 n個數 a1,a2...an。
現在他要求申徒嘉重新排列這些數，使得 H=||...|b1-b2|-b3|-b4|-...|-bn|最大（b 是
a 重新排列后的序列,|x|表示取 x的絕對值）
申徒嘉對于吹逼很擅長，但是數學就不怎么樣了，于是他請你來幫幫他。
【輸入格式】
第一行一個數 n，接下來一行n個數，第 i 個數表示a[i]
n<=300
1<=a[i]<=300
對于30%的數據，n<=10
【輸出格式】
輸出一行一個整數表示答案
【樣例輸入】
4
3 6 7 8
【樣例輸出】
6
【樣例解釋】
對于第一組樣例：
|||6-8|-3|-7| = 6
【題目分析】
亂搞做法：
因為答案不超過300，而且似乎要控制只有少數特定的排列使得答案最大是不太容易的，因此不斷隨機打亂更新答案，就很容易得到最大值。
【code】
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<ctime> #include<vector> using namespace std;const int N = 305; int n, a[N];inline int read(){int i = 0, f = 1; char ch = getchar();for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());if(ch == '-') f = -1, ch = getchar();for(; ch >= '0' && ch <= '9'; ch = getchar())i = (i << 3) + (i << 1) + (ch - '0');return i * f; }inline void wr(int x){if(x < 0) putchar('-'), x = -x;if(x > 9) wr(x / 10);putchar(x % 10 + '0'); }int main(){freopen("dcf.in", "r", stdin);freopen("dcf.out", "w", stdout);n = read();srand(time(0));for(int i = 1; i <= n; i++) a[i] = read();int T = 200000, ans = -1;while(T--){random_shuffle(a + 1, a + n + 1);int sum = a[1];for(int i = 2; i <= n; i++)sum = abs(sum - a[i]);if(sum > ans) ans = sum;}wr(ans);return 0; }
?
