题解 CF1012A 【Photo of The Sky】
MorsLin
2018-07-31 11:41:55
作为一个蒟蒻，$\tt{CF}$止步$Div.2\;C$
这个题主要考察思维，正解代码炒鸡短……
以下大部分搬运自[官方题解](http://codeforces.com/blog/entry/60920)
---
#### 题目大意：
给你一个长度为$2n$的数组，将这个数组分为两个可重集，每个集合有$n$个元素，使得这两个集合的极差之积最小，输出这个最小值
#### 题解：
假设输入的数组为$a[2n]$，为了方便，我们把要分成的两个可重集叫做$X$和$Y$
首先肯定要$sort$一下，使得数组有序，方便操作（下文提到的数组都是有序的）
接下来就是分类讨论了：
- 第一种情况：数组a的最大值和最小值都在$X$里。那么$X$的极差就是$a[2n]-a[1]$，接下来我们要使$Y$的极差尽量小，我们就需要枚举一下每个元素$a[i]$，因为集合里要有$n$个元素，所以对于每个$a[i]$，能使$Y$的极差最小的方式就是将$a[i]$~$a[i+n-1]$全部放到$Y$里，所以$Y$的极差就是$\min(a[i+n-1]-a[i])\;i\in [2,n+1]$
答案为 $\min((a[i+n-1]-a[i])\cdot(a[2n]-a[1]))\;i\in [2,n+1]$
- 第二种情况：最小值（$a[1]$）和最大值（$a[2n]$）分别在$X$和$Y$里。这样我们就要使$X$的最大值尽量小，$Y$的最小值尽量大，那么$X$的极差最小就为$a[n]-a[1]$，$Y$的极差最小为$a[2n]-a[n+1]$
答案为 $(a[n]-a[1])\cdot (a[2n]-a[n+1])$
最终的答案从这两种情况中取一个最小值就好了。
时间复杂度$O(nlogn)$（也就是排序的复杂度）
最后提醒一句：**别忘了开$\mathfrak{long\;long}$**
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int read(){
int k=0; char c=getchar();
for(;c<'0'||c>'9';) c=getchar();
for(;c>='0'&&c<='9';c=getchar())
k=(k<<3)+(k<<1)+c-48;
return k;
}
ll a[100010<<1],ans;
int main(){
int n=read();
for(int i=1;i<=n<<1;i++) a[i]=read();
sort(a+1,a+(n<<1)+1);
ans=(a[n]-a[1])*(a[n<<1]-a[n+1]); //第二种情况
for(int i=2;i<=n+1;i++) //第一种情况
ans=min((a[n<<1]-a[1])*(a[i+n-1]-a[i]),ans);
cout<<ans;
return 0;
}
```