E、蜗牛（时间限制: 1.0s 内存限制: 512.0MB）
【问题描述】
这天，一只蜗牛来到了二维坐标系的原点。 在 x 轴上长有 n 根竹竿。它们平行于 y 轴，底部纵坐标为 0 ，横坐标分别 为 x 1 , x 2 , ..., x n 。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 ( x n , 0) 。它只能在 x 轴上或者竹竿上爬行，在 x 轴
上爬行速度为 1 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行 的速度分别为 0 . 7 单位每秒和 1 . 3 单位每秒。 为了快速到达目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之间建立了传 送门（0 < i < n ），如果蜗牛位于第 i 根竹竿的高度为 a i 的位置 ( x i , a i ) ，就可以 瞬间到达第 i + 1 根竹竿的高度为 b i +1 的位置 ( x i +1 , b i +1 )， 请计算蜗牛最少需要多少秒才能到达目的地。
【输入格式】
输入共 1 + n 行，第一行为一个正整数 n ；
第二行为 n 个正整数 x 1 , x 2 , . . . , x n ；
后面 n − 1 行，每行两个正整数 a i , b i +1 。
【输出格式】
输出共一行，一个浮点数表示答案（ 四舍五入保留两位小数 ）。
【样例输入】
3 1 10 11 1 1 2 1
【样例输出】
4.20
【样例说明】
蜗牛路线：
(0 , 0) → (1 , 0) → (1 , 1) → (10 , 1) → (10 , 0) → (11 , 0) ，花费时间为 1 +1/ 0.7 + 0 + 1/1 .3 + 1 ≈ 4 . 20
【评测用例规模与约定】
对于 20 % 的数据，保证 n ≤ 15 ；
对于 100 % 的数据，保证 n ≤ 10⁵ ，a i , b i ≤ 10⁴ ，x i ≤ 10⁹ 。
Ⅰ、题目解读
dp[i][j] 表示蜗牛走到第 i 根杆子的最短用时，j 表示状态。
j = 0 : 走到杆子底部
j = 1 ：走到杆子的传送门处
P.S.由于只与前一个杆子状态有关，其实用两个变量就行，用二维数组便于理解
时间复杂度: O(n)
Ⅱ、代码
import java.io.*; import java.util.*; public class Main{ static int maxn = 200005,n,m; static long INF = (long)2e18,ans = 0,mod = (int)1e9+7; static Scanner sc = new Scanner (System.in); static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st =new StreamTokenizer(bf); static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[]args) throws IOException{ int T = 1; //T = Integer.parseInt(S()); while(T-->0) solve(); pw.flush(); } static final int I() throws IOException { st.nextToken(); return (int)st.nval; } static void solve() throws IOException{ n = I(); long x[] = new long [n+1]; for(int i=1;i<=n;i++) x[i] = I(); int []a = new int [n+1]; int []b = new int [n+1]; for(int i=1;i<n;i++) { a[i] = I();b[i] = I(); } double dp[][] = new double[n+1][2]; dp[1][0] = x[1]; //底端最小用时 dp[1][1] = x[1] + a[1] / 0.7; //传送门用时 for(int i=2; i<=n ; i++) { dp[i][0] = Math.min(dp[i-1][0]+x[i]-x[i-1], dp[i-1][1] + b[i-1]/1.3); dp[i][1] = Math.min(dp[i][0] + a[i] / 0.7, dp[i-1][1] + ((b[i-1]>a[i])?(b[i-1]-a[i])/1.3: (a[i]-b[i-1])/0.7)); } pw.printf("%.2f",dp[n][0]); } }
F、合并区域 （时间限制: 2.0s 内存限制: 512.0MB）
【问题描述】
小蓝在玩一款种地游戏。现在他被分配给了两块大小均为 N × N 的正方形 区域。这两块区域都按照 N × N 的规格进行了均等划分，划分成了若干块面积 相同的小区域，其中每块小区域要么是岩石，要么就是土壤，在垂直或者水平 方向上相邻的土壤可以组成一块土地。现在小蓝想要对这两块区域沿着边缘进 行合并，他想知道合并以后可以得到的最大的一块土地的面积是多少（土地的 面积就是土地中土壤小区域的块数）？ 在进行合并时，小区域之间必须对齐。可以在两块方形区域的任何一条边 上进行合并，可以对两块方形区域进行 90 度、 180 度、 270 度、 360 度的旋转， 但不可以进行上下或左右翻转，并且两块方形区域不可以发生重叠。
【输入格式】
第一行一个整数 N 表示区域大小。 接下来 N 行表示第一块区域，每行 N 个值为 0 或 1 的整数，相邻的整数 之间用空格进行分隔。值为 0 表示这块小区域是岩石，值为 1 表示这块小区域 是土壤。 再接下来 N 行表示第二块区域，每行 N 个值为 0 或 1 的整数，相邻的整 数之间用空格进行分隔。值为 0 表示这块小区域是岩石，值为 1 表示这块小区 域是土壤。
【输出格式】
一个整数表示将两块区域合并之后可以产生的最大的土地面积。
【样例输入】
4 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1
15
【样例说明】
第一张图展示了样例中的两块区域的布局。第二张图展示了其中一种最佳
的合并方式，此时最大的土地面积为 15。
【评测用例规模与约定】
对于 30 % 的数据， 1 ≤ N ≤ 5 。
对于 60 % 的数据， 1 ≤ N ≤ 15 。
对于 100 % 的数据， 1 ≤ N ≤ 50
Ⅰ、题目解读
题目会给你两块土地，你可以进行两块土地的“缝合”，求最大的连续的土地。
最大土地有三种情况
①、左右连接成一块最大的土地
②、单独一边中间是最大的土地
③、因为另一块土地的连接而导致原本不连接的土地也连接成新的土地（这种情况是我没想到的）
我只想到了前面两种情况，如果要算上第三种情况的话就应该使用暴力求解（毕竟数据量并不是很大），不断拼接，求最大连续的土地。我的代码也只是符合前面两种情况，有正确代码还请大佬给出。万分感谢。
Ⅱ、代码
import java.awt.*; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Scanner; public class Main { static class Point{ int x,y; public Point(int x, int y) { this.x = x; this.y = y; } } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[][] arr1=new int[n+2][n+2];//第一个矩阵 int[][] arr2=new int[n+2][n+2];//第二个矩阵 for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ arr1[i][j]=sc.nextInt(); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ arr2[i][j]=sc.nextInt(); } int max=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ if (arr1[i][j]==1){ length(arr1,i,j); List<Point> list=new ArrayList<>(set); for (Point p:list) arr1[p.x][p.y]=sum; max=Math.max(max,sum);//防止矩阵里面是最大的 sum=0; set.clear(); } } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ if (arr2[i][j]==1){ length(arr2,i,j); List<Point> list=new ArrayList<>(set); for (Point p:list) arr2[p.x][p.y]=sum; max=Math.max(max,sum);//防止矩阵里面是最大的 sum=0; set.clear(); } } int l=0; int r=0; //求四边的最大值然后拼接 //两行 for (int i=1;i<=n;i+=(n-1)) for (int j=1;j<=n;j++){ l=Math.max(l,arr1[i][j]); r=Math.max(r,arr2[i][j]); } //两列 for (int i=1;i<=n;i++) for (int j=1;j<=n;j+=(n-1)){ l=Math.max(l,arr1[i][j]); r=Math.max(r,arr2[i][j]); } max=Math.max(max,l+r); System.out.println(max); } static int sum=0; static HashSet<Point> set=new HashSet<>(); public static void length(int[][] arr, int i, int j){ sum++; arr[i][j]=0; Point p=new Point(i,j); set.add(p); if (arr[i-1][j]==1) length(arr,i-1,j); if (arr[i+1][j]==1) length(arr,i+1,j); if (arr[i][j-1]==1) length(arr,i,j-1); if (arr[i][j+1]==1) length(arr,i,j+1); } }
G、买二赠一（时间限制: 1.0s 内存限制: 512.0MB）
【问题描述】
某商场有 N 件商品，其中第 i 件的价格是 A i 。现在该商场正在进行 “ 买二 赠一” 的优惠活动，具体规则是： 每购买 2 件商品，假设其中较便宜的价格是 P （如果两件商品价格一样，
则 P 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P /2 的商品，免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商 品，但是每件商品只能被购买或免费获得一次。 小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？
【输入格式】
第一行包含一个整数 N 。
第二行包含 N 个整数，代表 A 1 , A 2 , A 3 , . . . ， A N
【输出格式】
输出一个整数，代表答案。
【样例输入】
7 1 4 2 8 5 7 1
【样例输出】
25
【样例说明】
小明可以先购买价格 4 和 8 的商品，免费获得一件价格为 1 的商品；再后
买价格为 5 和 7 的商品，免费获得价格为 2 的商品；最后单独购买剩下的一件
价格为 1 的商品。总计花费 4 + 8 + 5 + 7 + 1 = 25 。不存在花费更低的方案。
【评测用例规模与约定】
对于 30 % 的数据， 1 ≤ N ≤ 20 。
对于 100 % 的数据， 1 ≤ N ≤ 5 × 10⁵ ，1 ≤ A i ≤ 10⁹ 。
Ⅰ、题目解读
要花费最少，就要购买的商品价格高点，这样可以白嫖到更贵的商品，而不是便宜的商品。如题目所给样例：7+8（2）+4+5（1）+1=25。我认为可以使用数组储存再sort排序，然后使用二分查找到符合小于p/2的最大值，再将已经买完的商品变为0（或者其他方法标记为已购买的状态），然后不断重复上面步骤。（博主使用word打开题目，题目有问题，p/2显示的是p2，看错题目了，纯纯大冤种😭😭😭）。
Ⅱ、代码1(复杂度过大，超时)
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); long[] arr=new long[n]; for (int i=0;i<n;i++){ arr[i]=sc.nextInt(); } //进行排序商品 Arrays.sort(arr); long sum=0; //arr数组中全为0才可以退出循环，因为全部东西都需要购买 while (arr[arr.length-1]!=0){ //尽量买大的商品，这样可以尽量白嫖到更贵的商品 long k=arr[arr.length-2]/2; sum+=(arr[arr.length-2]+arr[arr.length-1]); //开始二分查找 int l=0,r=arr.length-1; int mid=(l+r)/2; while (l<=r){ if (arr[mid]>k){ r=mid-1; }else if (arr[mid]<k){ l=mid+1; }else { break; } mid=(l+r)/2; } //将商品设置为已购买的状态 arr[mid]=0; arr[arr.length-2]=0; arr[arr.length-1]=0; Arrays.sort(arr); } System.out.println(sum); } }
或者创建 用来判断 是否已购买的boolean数组 来进行判断
代码2（正确答案）
import java.util.*; import java.io.*; public class Main { static int n,m,mod=(int)1e9+7,maxn=500010; static long ans=0,INF=(long)1e18; static Scanner sc = new Scanner (System.in); static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st = new StreamTokenizer(bf); static PrintWriter pw = new PrintWriter(System.out); public static void main(String[]args) throws IOException{ int T = 1; //T = I(); while(T-->0) solve(); pw.flush(); } static int I() throws IOException{ st.nextToken(); return (int)st.nval; } static int a[] = new int [maxn]; static boolean f[] = new boolean [maxn]; static int find(int x) { int l=1,r=n; int res =0; while(l<=r) { int mid = (l+r)/2; if(f[mid]) { //先前赠送过，跳到左边 r=mid-1;continue; } if(a[mid] <= x) { res = Math.max(res, mid); l = mid+1; } else r = mid-1; } return res; } static void solve() throws IOException{ n = I(); for(int i=1 ;i<=n;i++) a[i] =I(); Arrays.sort(a,1,n+1); int t = 0; for(int i=n;i>=1;i--) { if(f[i]) continue;//赠送过，跳过 ans += a[i]; t++; if(t == 2) { t=0; int id = find(a[i]/2); if(id>0) f[id]=true; } } pw.println(ans); } }
H、合并石子（时间限制: 1.0s 内存限制: 512.0MB）
【问题描述】
在桌面从左至右横向摆放着 N 堆石子。每一堆石子都有着相同的颜色，颜 色可能是颜色 0 ，颜色 1 或者颜色 2 中的其中一种。 现在要对石子进行合并，规定每次只能选择位置相邻并且颜色相同的两堆 石子进行合并。合并后新堆的相对位置保持不变，新堆的石子数目为所选择的 两堆石子数目之和，并且新堆石子的颜色也会发生循环式的变化。具体来说： 两堆颜色 0 的石子合并后的石子堆为颜色 1 ，两堆颜色 1 的石子合并后的石子堆为颜色 2 ，两堆颜色 2 的石子合并后的石子堆为颜色 0 。本次合并的花费为所 选择的两堆石子的数目之和。 给出 N 堆石子以及他们的初始颜色，请问最少可以将它们合并为多少堆石子？如果有多种答案，选择其中合并总花费最小的一种，合并总花费指的是在 所有的合并操作中产生的合并花费的总和。
【输入格式】
第一行一个正整数 N 表示石子堆数。
第二行包含 N 个用空格分隔的正整数，表示从左至右每一堆石子的数目。
第三行包含 N 个值为 0 或 1 或 2 的整数表示每堆石头的颜色。
【输出格式】
一行包含两个整数，用空格分隔。其中第一个整数表示合并后数目最少的
石头堆数，第二个整数表示对应的最小花费。
【样例输入】
5 5 10 1 8 6 1 1 0 2 2
【样例输出】
2 44
【样例说明】
上图显示了两种不同的合并方式。其中节点中标明了每一堆的石子数目，
在方括号中标注了当前堆石子的颜色属性。左图的这种合并方式最终剩下了两
堆石子，所产生的合并总花费为 15 + 14 + 15 = 44 ；右图的这种合并方式最终
也剩下了两堆石子，但产生的合并总花费为 14 + 15 + 25 = 54 。综上所述，我
们选择合并花费为 44 的这种方式作为答案。
【评测用例规模与约定】
对于 30 % 的评测用例， 1 ≤ N ≤ 10 。
对于 50 % 的评测用例， 1 ≤ N ≤ 50 。
对于 100 % 的评测用例， 1 ≤ N ≤ 300 , 1 ≤ 每堆石子的数目 ≤ 1000 。
Ⅰ、题目解读
这题和G买二赠一有点类似，都是合并然后选择某种方法标记为已合并的状态。我举个例子（1，5）和（1，10）合并为（2，15），另一个变成已使用的状态（3，0），之后进行二维数组排序，先排石子的颜色（0，1，2）,在排石子的数量（升序排），因为这样才能保证花费最小（开始合并也要进行一道排序）。不断重复上面步骤计算花费，直到没有一样的石子可以合并了（3为已使用状态不可以合并）。但是这上面有一个漏洞，我们可以看下面一组数据就懂了：（0，10），（0，11），（1，1），（1，2），（2，3）；如果按照上面的思路就是先合并（0，10）和（0，11），但是我们用肉眼就可以看出来应该先合并（1，1），（1，2）->(2,3)和（3，0），然后两个（2，3）变成（0，6）和（3，0），再去合并颜色为0的石子，因此合并的时候要去寻找一下不同石子可以合并的最小费用，优先合并花费少的。
Ⅱ、代码
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[][] arr=new int[n][2]; for (int i=0;i<n;i++){ arr[i][1]=sc.nextInt(); } for (int i=0;i<n;i++){ arr[i][0]=sc.nextInt(); } //先进行石子排序，在进行不同石子的数量排序 Arrays.sort(arr,(o1, o2) -> { if (o1[0]==o2[0]) return o1[1]-o2[1]; return o1[0]-o2[0]; }); boolean merge=false;//判断是否有过合并，如果没有过合并即退出循环 int sum=0;//所需花费 //n=1，无需合并，直接输出 if (n==1){ System.out.println(1+" "+0); return; } while (true){ int k=0;//用来记录合并石子的下标 int SumMin=9999;//用来记录当前最小的合并花费 boolean a=true;//第一次找到0 boolean b=true;//第一次找到1 for (int i=1;i<n&&arr[i][0]!=3;i++){ if (arr[i-1][0]==0&&arr[i][0]==0&&a){ k=i; a=false; SumMin=Math.min(SumMin,arr[i][1]+arr[i-1][1]); merge=true; } if (arr[i-1][0]==1&&arr[i][0]==1&&b){ if (SumMin>arr[i][1]+arr[i-1][1]){ k=i; SumMin=(arr[i][1]+arr[i-1][1]); } b=false; merge=true; } if (arr[i-1][0]==2&&arr[i][0]==2){ if (SumMin>arr[i][1]+arr[i-1][1]){ k=i; SumMin=(arr[i][1]+arr[i-1][1]); } merge=true; break; } } if (!merge) break; sum+=SumMin; //合并石子之后，变换成新的颜色0，1，2 if (arr[k][0]==0){ arr[k-1][0]=1; }else if (arr[k][0]==1){ arr[k-1][0]=2; }else { arr[k-1][0]=0; } arr[k-1][1]=SumMin; //将已合并的石子设置为使用状态 arr[k][0]=3; arr[k][1]=0; merge=false; //进行进行排序 Arrays.sort(arr,(o1, o2) -> { if (o1[0]==o2[0]) return o1[1]-o2[1]; return o1[0]-o2[0]; }); } int l=0;//查找当前还有几堆石子 for (int i=0;i<n&&arr[i][0]!=3;i++){ l++; } System.out.println(l+" "+sum); } }
I、最大开支（时间限制: 1.0s 内存限制: 512.0MB ）
【问题描述】
小蓝所在学校周边新开业了一家游乐园，小蓝作为班长，打算组织大家去 游乐园玩。已知一共有 N 个人参加这次活动，游乐园有 M 个娱乐项目，每个 项目都需要买门票后才可进去游玩。门票的价格并不是固定的，团购的人越多 单价越便宜，当团购的人数大于某个阈值时，这些团购的人便可以免费进入项 目进行游玩。这 M 个娱乐项目是独立的，所以只有选择了同一个项目的人才可 以参与这个项目的团购。第 i 个项目的门票价格 H i 与团购的人数 X 的关系可 以看作是一个函数：
Hi(X) = max (Ki × X + Bi , 0) ，
max 表示取二者之中的最大值。当 H i = 0 时说明团购人数达到了此项目的免单阈值。 这 N 个人可以根据自己的喜好选择 M 个娱乐项目中的一种，或者有些人 对这些娱乐项目都没有兴趣，也可以选择不去任何一个项目。每个人最多只会 选择一个娱乐项目，如果多个人选择了同一个娱乐项目，那么他们都将享受对 应的团购价格。小蓝想知道他至少需要准备多少钱，使得无论大家如何选择， 他都有能力支付得起所有 N 个人购买娱乐项目的门票钱。
【输入格式】
第一行两个整数 N 、 M ，分别表示参加活动的人数和娱乐项目的个数。 接下来 M 行，每行两个整数，其中第 i 行为 K i 、 B i ，表示第 i 个游乐地点 的门票函数中的参数。
【输出格式】
一个整数，表示小蓝至少需要准备多少钱，使得大家无论如何选择项目， 自己都支付得起。
【样例输入】
4 2 -4 10 -2 7
【样例输出】
12
【样例说明】
样例中有 4 个人， 2 个娱乐项目，我们用一个二元组 ( a , b ) 表示 a 个人选 择了第一个娱乐项目，b 个人选择了第二个娱乐项目，那么就有 4 − a − b 个 人没有选择任何项目，方案 ( a , b ) 对应的门票花费为 max ( − 4 × a + 10 , 0) × a + max ( − 2 × b + 7 , 0) × b ，所有的可能如下所示：
其中当 a = 1, b = 2 时花费最大，为 12。此时 1 个人去第一个项目，所以第一个项目的单价为 10 − 4 = 6，在这个项目上的花费为 6 × 1 = 6；2 个人去 第二个项目，所以第二个项目得单价为 7 − 2 × 2 = 3，在这个项目上的花费为 2 × 3 = 6；还有 1 个人没去任何项目，不用统计；总花费为 12，这是花费最大的一种方案，所以答案为 12。
【评测用例规模与约定】
对于 30 % 的评测用例， 1 ≤ N , M ≤ 10 。
对于 50 % 的评测用例， 1 ≤ N , M ≤ 1000 。
对于 100 % 的评测用例， 1 ≤ N , M , B i ≤ 10⁵ ，−10⁵ ≤ K i < 0 。
Ⅰ、题目解读
这题的解题思路就是：计算每个项目多一个人参加时造成的费用变化量，贪心的参加费用变化最多的项目。
J、魔法阵（时间限制: 1.0s 内存限制: 512.0MB ）
【输入格式】
第一行输入三个整数， N , K , M ，用空格分隔。
接下来 M 行，每行包含三个整数 u , v , w ，表示结点 u 与结点 v 之间存在一
条伤害属性为 w 的无向边。
【输出格式】
输出一行，包含一个整数，表示小蓝从结点 0 到结点 N − 1 受到的最小伤 害。
【样例输入 1】
4 2 3 0 1 2 1 2 1 2 3 4
【样例输出 1】
2
【样例输入 2】
2 5 1 0 1 1
【样例输出 2】
0
【样例说明】
样例 1 ，存在路径： 0 → 1 → 2 → 3 ， K = 2 ，如果在 0 → 1 → 2 上使用魔 法，那么答案就是 0 + 0 + 4 = 4 ；如果在 1 → 2 → 3 上使用魔法，那么答案就 是 2 + 0 + 0 = 2 。再也找不到比 2 还小的答案了，所以答案就是 2 。 样例 2 ，存在路径： 0 → 1 → 0 → 1 → 0 → 1 ， K = 5 ，这条路径总计恰好 走了 5 条边，所以正好可以用魔法消除所有伤害，答案是 0 。
【评测用例规模与约定】
对于 30 % 的评测用例， 1 ≤ N ≤ 20 。
对于 50 % 的评测用例， 1 ≤ N ≤ 100 。
对于 100 % 的评测用例， 1 ≤ N ≤ 1000 , 1 ≤ M ≤ N × ( N−1) /2 ，1 ≤ K ≤ 10 , 0 ≤ u , v ≤ N − 1 ， 1 ≤ w ≤ 1000 。
