# AtCoder Regular Contest 121 D - 1 or 2

### Problem Statement

Snuke has a blackboard and N N candies. The tastiness of the i i -th candy is ai a i .

He will repeat the operation below until he has no more candy.

• Choose one or two of his candies and eat them (of course, they disappear). Then, write on the blackboard the total tastiness of the candies he has just chosen.

Snuke wants to minimize XY X − Y , where X X and Y Y are the largest and smallest values written on the blackboard, respectively. Find the minimum possible value of XY X − Y .

### Constraints

• All values in input are integers.
• 1N5000 1 ≤ N ≤ 5000
• 109ai109 − 10 9 ≤ a i ≤ 10 9

### Input

Input is given from Standard Input in the following format:

```N   N
a1    a    1     a2    a    2     ⋯   ⋯   aN    a   N
```

### Output

Print the minimum possible value of XY X − Y , where X X and Y Y are the largest and smallest values written on the blackboard, respectively.

```3
1 2 4
```

### Sample Output 1

```1
```
• One optimal sequence of operations is to eat the candies with the tastinesses of 1 1 and 2 2 in the first operation, and then eat the candies with the tastiness of 4 4 in the second operation.

```2
-100 -50
```

### Sample Output 2

```0
```
• It is optimal to eat both candies with the tastiness of 100 − 100 and 50 − 50 in the first operation.

### Sample Input 3

```20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38
```

```13
```

## 题解

\[a_1,a_2,a_3......a_i,a_{i+1},......a_n \]

\[a_1+a_n,a_2+a_{n-1}.....a_{i-1}+a_{n-i+2} \]

\[a_i,a_{i+1},a_{i+2}.....a_{j} \]

``````const int N=3e5+5;

ll n, m, _;
int i, j, k;
//ll a[N];
vector<ll> v;

ll calc(int sz)
{
int l = 0, r = sz - 1;
ll maxx = -1e18, minn = 1e18;
while(r >= l){
if(l == r){
minn = min(minn, v[l]);
maxx = max(maxx, v[l]);
break;
}
else{
minn = min(minn, v[r] + v[l]);
maxx = max(maxx, v[r] + v[l]);
}
r--;
l++;
}
return maxx - minn;
}

signed main()
{
//IOS;
while(~sd(n)){
rep(i, 0, n - 1) sll(_), v.pb(_);
sort(all(v));
ll minn = calc(n);
rep(i, 1, n - 1){
v.pb(0);
sort(all(v));
minn = min(minn, calc(n + i));
}
pll(minn);
v.clear();
}
//PAUSE;
return 0;
}
``````

• 分享:

发表评论 说点什么