[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] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology