[TIOJ] 1367. 神根島的密室

題目連結:http://tioj.infor.org/problems/1367
經典的排序不等式題目,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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

[IOJ] 19. 啦啦啦

[IOJ] 14. 費氏數列問題