第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-53 最小乘积(基本型)
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
算法训练 最小乘积(基本型)
资源限制
内存限制：512.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
给两组数，各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
题解：
C语言
1#include<stdio.h> void sort1(int *a,int n) { int i,j; int tmp; for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++) if(a[j]>a[j+1]) { tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; } } void sort2(int *a,int n) { int i,j; int tmp; for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++) if(a[j]<a[j+1]) { tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; } } int main(void) { int T; int n,i; int total; int a[8],b[8],c[8]; scanf("%d",&T); while(T) { total=0; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) scanf("%d",&b[i]); sort1(a,n); sort2(b,n); for(i=0;i<n;i++) c[i]=a[i]*b[i]; for(i=0;i<n;i++) total+=c[i]; printf("%d\n",total); T--; } return 0; }
C++语言
#include<iostream> #include<algorithm> using namespace std; int a[8],b[8]; int main() { int T,n; int i,j; cin>>T; while(T--) { int sum=0; cin>>n; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<n;i++) cin>>b[i]; sort(a,a+n); sort(b,b+n); for(i=0;i<n;i++) { sum+=a[i]*b[n-1-i]; } cout<<sum<<endl; } return 0; }
Java语言
在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static DATE[] date; /*数据储存*/ static class DATE{ int[] a; int[] b; int n; int sum; DATE(int n,int a[],int b[]){ Arrays.sort(a); Arrays.sort(b); this.n=n; this.a=new int[n]; this.b=new int[n]; for(int i=0;i<n;i++) { this.a[i]=a[i]; this.b[i]=b[i]; } this.sum=sum(); } int sum() { int start=0,end=n-1,sum=0; while(start!=n) { sum=sum+a[start]*b[end]; start++; end--; } return sum; } } /*流输入转换int型*/ static int read_int(BufferedReader input) throws IOException { int temp_1=input.read(); while(temp_1==10||temp_1==13||temp_1==32) temp_1=input.read(); int temp,key=1; while(temp_1==45) { key*=-1; temp_1=input.read(); } temp=temp_1-'0'; int temp_2=input.read(); while(temp_2!=10&&temp_2!=13&&temp_2!=32) { temp=temp*10+(temp_2-'0'); temp_2=input.read(); } return temp*key; } public static void main(String[] args) throws IOException { /*数据初始化*/ BufferedReader input =new BufferedReader(new InputStreamReader(System.in)); int T=read_int(input); date=new DATE[T]; for(int i=0;i<T;i++) { int n=read_int(input); int[] a=new int[n]; int[] b=new int[n]; for(int j=0;j<n;j++) a[j]=read_int(input); for(int j=0;j<n;j++) b[j]=read_int(input); date[i]=new DATE(n,a,b); } input.close(); for(int i=0;i<T;i++) System.out.println(date[i].sum); } }
Python语言
相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。
n=int(input()) num=0 list2=[] list1=[] list3=[] if n<=0: print("") else: while True: y=int(input()) z=input() m=input() z=z.split() m=m.split() for i in z: i=int(i) list2.append(i) for j in m: j=int(j) list3.append(j) num+=1 list2.sort() count=0 while True: maxnum=max(list2) mixnum=min(list3) number= maxnum * mixnum list2.remove(maxnum) list3.remove(mixnum) count=count+number if list2 ==[] and list3==[]: list1.append(count) break if num == n: break for index in list1: print(index)
总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
