题解 CF1012A 【Photo of The Sky】

MorsLin · 2018-07-31 11:41:55 · 题解

作为一个蒟蒻，\tt{CF}止步Div.2\;C

这个题主要考察思维，正解代码炒鸡短……

以下大部分搬运自官方题解

题目大意：

给你一个长度为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;
}