关键词:
题目&思路:
代码:
import java.util.*;
public class MinimumCostSort
public static final int MAX = 1000;
public static void main(String[] args)
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int A[] = new int[n+1];
boolean T[] = new boolean[n+1];//用于判断数组中的元素是否已经被处理过了
int min_val = Integer.MAX_VALUE;
for (int i=1;i<=n;i++)
A[i] = cin.nextInt();
T[i] = false;
min_val = Math.min(min_val, A[i]);
int[] B = getPosition(A);//获取位置排序
ArrayList<ArrayList<Integer>> Group = new ArrayList<>();//用于存放每一个组
for (int i =1;i<=n;i++)
ArrayList<Integer> S = new ArrayList<>();
int u = i;
while (!T[u])//如果当前值没有处理过,才进入循环进行处理
T[u] = true;//当前数字设置为已被处理
S.add(A[u]);//将当前节点添加到集合S中
u = B[u];//该数字作为新的索引
//集合S构建完后,添加到Group里
if(S.size()!=0)
Group.add(S);
int cost = 0;
for (int i=0;i<Group.size();i++)
int sub_cost = subCost(Group.get(i), min_val);
cost += sub_cost;
System.out.println(cost);
public static int[] getPosition(int[] A)
int n = A.length-1;
ArrayList<Integer> C = new ArrayList<>();
for (int i=0;i<=n;i++)
C.add(A[i]);
Collections.sort(C);
int[] B = new int[n+1];
for (int i=0;i<=n;i++)
B[i] = C.indexOf(A[i]);
return B;
public static int subCost(ArrayList<Integer> S, int min_val)
int sub_cost = 0;
int w = 0;
int n = S.size();
int min_w = Integer.MAX_VALUE;
for (int i=0;i<n;i++)
w = w + S.get(i);
min_w = Math.min(min_w, S.get(i));
if (S.indexOf(min_val)!=-1)//最小是在集合内
sub_cost = w + (n-2)*min_w;
else
sub_cost = Math.min(w + min_w + (n+1) * min_val, w + (n-2)*min_w);
return sub_cost;
输入1:
7
4 3 2 7 1 6 5
输出1:
24
输入2:
5
1 5 3 4 2
输出2:
5
输入3:
6
2 1 8 10 7 9
输出3:
49
挑战程序设计竞赛(算法和数据结构)——10.3最大堆(最小堆)的java实现(代码片段)
题目:这一小节的思路很好,仍然是使用了一个递归,值得注意的是,数组长度的一半这个值恰好是下标最大的非叶节点:代码如下:importjava.util.Scanner;publicclassMaxHeappublicstaticvoidmain(String[]args)Scannercin=ne... 查看详情
挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现
题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情
挑战程序设计竞赛(算法和数据结构)——4.5java中对应c++stl的数据结构类
挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现(代码片段)
题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情
挑战程序设计竞赛(算法和数据结构)——17.4最大正方形的java实现(代码片段)
题目&思路:代码:importjava.util.Scanner;publicclassLargestSquarepublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intH=cin.nextInt();intW=cin.nextInt();intmap[] 查看详情
挑战程序设计竞赛(算法和数据结构)——5.5迭代器和二分查找的java实现(代码片段)
迭代器代码:importjava.util.Arrays;importjava.util.Iterator;publicclassIteratorDemopublicstaticvoidmain(String[]args)int[]arr=newint[]1,2,3,4,5,6,7,8,9,8,2,6,5,7,1,3,4,5,6;Iterator<Integer 查看详情
挑战程序设计竞赛(算法和数据结构)——5.4散列法习题java代码实现(代码片段)
题目:散列法相关的代码可以参考之前一篇博文https://blog.csdn.net/weixin_42887138/article/details/121254659importjava.lang.ref.PhantomReference;importjava.util.Scanner;publicclass_5_4publicstaticvoidmain(String[]arg 查看详情
挑战程序设计竞赛(算法和数据结构)——4.6数据结构的应用——计算面积java代码实现(代码片段)
题目:代码及实现思路如下:importjava.io.BufferedInputStream;importjava.util.Scanner;importjava.util.Stack;importjava.util.Vector;publicclass_4_6publicstaticvoidmain(String[]args)/*设计两个栈,S1和S 查看详情
挑战程序设计竞赛(算法和数据结构)——7.6逆序数的java实现(代码片段)
逆序数的题简单来说就可以归化成判断归并排序需要交换几次的问题,因此代码可以直接沿用归并排序。思路讲解:importjava.io.BufferedInputStream;importjava.util.Scanner;publicclassInversionNumberpublicstaticvoidmain(String[]args)Scannercin=newS... 查看详情
挑战程序设计竞赛(算法和数据结构)——4.3队列习题的java实现(代码片段)
题目:基本思路:将任务定义为一个包含名称和时间的Task类,定义一个Task类型的队列,并循环下列算法:用时间sum_time来记录处理情况,只要队列不为空,就不断执行当处理一个队头任务时,首先... 查看详情
挑战程序设计竞赛(算法和数据结构)——13.1基于加权图的两类问题的描述
最小生成树树是没有环的图。在树中,任意顶点rrr和vvv之间必然存在着1条路径。图G=(V,E)G=(V,E)G=(V,E)的生成树G=(V′,E′)G=(V',E')G=(V′,E′)是图GGG的子图,它拥有图GGG所有的顶点V(V=V′)V(V=V')V(... 查看详情
挑战程序设计竞赛(算法和数据结构)——4.4链表习题的java实现(代码片段)
链表有初始化、插入元素、删除元素、查找元素等方法。在创建链表的过程中,最关键的是搞清楚链表的几个关键数据构成:链表由一个个节点互相串联构成,节点作为一个基础的对象,可由类Node(随便取个... 查看详情
挑战程序设计竞赛(算法和数据结构)——分割(下)&快速排序的java实现(代码片段)
在《挑战程序设计竞赛(算法和数据结构)——7.2分割(上)JAVA实现》中实现了将任一数组的元素以最后一个元素为界,小的排在前,大的排在后的功能,参照以下链接:https://blog.csdn.net/weixin_42887... 查看详情
挑战程序设计竞赛(算法和数据结构)——16.13线段相交问题(曼哈顿算法)的java实现(代码片段)
题目与思路:代码:importjava.util.*;publicclassManhattanGeometrypublicstaticclassEpElementprivateGraghBasic.PointP;privateStringdirection;//left,right,bottom,topprivateintid;EpElement()EpElement(GraghBasic.PointP,Stringdirection,intid)this.P=P;this.direction=direction;this... 查看详情
挑战程序设计竞赛(算法和数据结构)——16.12凸包(安德鲁算法)的java实现(代码片段)
题目与思路:代码:importjava.util.*;//数据结果套数据结构时,需要一层一层初始化publicclassConvexHullpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();Vector<GraghBasic.Point>S=newVector<GraghBasic.Poi... 查看详情
挑战程序设计竞赛(算法和数据结构)——13.3单源最短路径(dijkstra算法)的java实现(代码片段)
题目:代码:importjava.io.BufferedInputStream;importjava.io.BufferedReader;importjava.util.Scanner;publicclassSingleSourceShortestPathpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();//初始化邻接矩阵MintM[][]... 查看详情
挑战程序设计竞赛(算法和数据结构)——12.2图的表示java实现(代码片段)
题目:importjava.util.Scanner;publicclassGraphImplementpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();//建立图的邻接矩阵intM[][]=newint[n][n];for(inti=0;i<n;i++)intid=cin.nextInt();intdegree=cin.nextInt();for(i... 查看详情
挑战程序设计竞赛(算法和数据结构)——7.2分割(上)java实现(代码片段)
题目:思路:示例1:示例2:代码如下:importjava.io.BufferedInputStream;importjava.util.Scanner;publicclassPartitionpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();int[]A=newint[n];for(inti=... 查看详情