[TIOJ] 1367. 神根島的密室
題目連結:http://tioj.infor.org/problems/1367
經典的排序不等式題目,greedy做就好了,把a數列最小的跟b數列最大的乘+a數列次小乘以b數列次大的...就會得到最小值,詳細證明可以查一下,因為不難找的到,這邊就不放了。
經典的排序不等式題目,greedy做就好了,把a數列最小的跟b數列最大的乘+a數列次小乘以b數列次大的...就會得到最小值,詳細證明可以查一下,因為不難找的到,這邊就不放了。
#include <bits/stdc++.h>
using namespace std;
#define N 50000
int arr1[N+5],arr2[N+5];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)scanf("%d",&arr1[i]);
for(int i=0;i<n;i++)scanf("%d",&arr2[i]);
sort(arr1,arr1+n,[](int a,int b){return a<b;});
sort(arr2,arr2+n,[](int a,int b){return a>b;});
unsigned long long ans=0;
for(int i=0;i<n;i++) ans+=(unsigned long long)arr1[i]*(unsigned long long)arr2[i];
printf("%llu\n",ans);
}
return 0;
}
留言
張貼留言