CF1631A Min Max Swap 题解

题目传送门

题意简述

给定数组 \(a\) 和 \(b\),可以交换下标相同的两个元素。让 \(a\) 数组的最大值和 \(b\) 数组的最大值之积最小。

分析

想象一个长方形,它的周长是固定的,那怎么分配长和宽才能让面积尽可能的小呢?

就假设周长是 \(18\),则长宽之和是 \(9\),列下表格:

面积
1 8 8
2 7 14
3 6 18
4 5 20

观察长和宽的差值,分别是 \(7,5,3,1\),而面积不断地增大。

所以我们可以得出结论:

两个数和一定,差越大,积越小。

回到题目,题目要求积要尽可能地小,所以我们让 \(a\) 数组的数尽可能地大,\(b\) 数组的数尽可能地小,再分别求最大值,就能得出答案了。

代码实现

#include <bits/stdc++.h>
using namespace std;

int t;
int n;
int a[105];
int b[105];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        int s1=0,s2=0;
        for(int i=1;i<=n;i++){
            if(a[i]<b[i])swap(a[i],b[i]);
            s1=max(s1,a[i]);s2=max(s2,b[i]);
        }
        cout<<s1*s2<<endl;
    }
    return 0;
}
上一篇:滑雪(百炼1088)


下一篇:高精度加减乘除