問題描述
　　給兩組數，各n個。
　　請調整每組數的排列順序，使得兩組數據相同下標元素對應相乘，然后相加的和最小。要求程序輸出這個最小值。
　　例如兩組數分別為:1 3　　-5和-2 4 1

那么對應乘積取和的最小值應為：
　　(-5) * 4 + 3 * (-2) + 1 * 1 = -25
輸入格式
　　第一個行一個數T表示數據組數。后面每組數據，先讀入一個n，接下來兩行每行n個數，每個數的絕對值小于等于1000。
　　n<=8,T<=1000
輸出格式
　　一個數表示答案。
樣例輸入
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

樣例輸出

-25
6

本來就是一個水題,昨天晚上在宿舍沒好好看題,忙著做完了去看電影,就直接wa了.下載下來樣例看了看,什么玩意.今天早上看到后突然發先是相同位置的元素乘積…將一個序列正著排序,另一個倒著排序,這樣就好了…我一開始用了一個全排列函數,耗時812ms.幸虧數據量小.吼吼吼
代碼如下

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=10; int a[maxx]; int b[maxx]; int n;int main() {int t;while(scanf("%d",&t)!=EOF){while(t--){scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&a[i]);for(int i=0;i<n;i++) scanf("%d",&b[i]);sort(b,b+n);ll maxn=inf;do{ll ans=0;for(int i=0;i<n;i++){ans+=a[i]*b[i];}maxn=min(ans,maxn);}while(next_permutation(b,b+n));//練習一下全排列函數,嘿嘿printf("%I64d\n",maxn);}} }

努力加油a啊,(^o)/~

總結

以上是生活随笔為你收集整理的算法训练 最小乘积(基本型) (蓝桥杯水题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。