Contestant. Rank 3946. Rating +15 (+165 -150).
A. Make it Beautiful
题意
给定一个数组
思路
将数组降序排列即可。
需要特判一种情况,当降序排列后,第一个数和第二个数重复,那么需要向后枚举,找到第一个不一样的数,将其和第一个数交换即可。若没有这个数,输出
时间复杂度:最坏
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
nxt:while(t -- > 0){
int n = scanner.nextInt();
int[] sum = new int[n + 1];
Integer[] a = new Integer[n];
for(int i=0;i<n;i++) a[i] = scanner.nextInt();
Arrays.sort(a, (o1, o2) -> o2 - o1);
if(a[0] != a[1]){
System.out.println("YES");
for(int i=0;i<n;i++) System.out.printf("%d ", a[i]);
System.out.println();
continue nxt;
}
boolean flag = false;
for(int i=2;i<n;i++){
if(a[i] != a[1]){
int tmp = a[i]; a[i] = a[1]; a[1] = tmp;
flag = true;
break;
}
}
if(flag){
System.out.println("YES");
for(int i=0;i<n;i++) System.out.printf("%d ", a[i]);
System.out.println();
}else System.out.println("NO");
}
}
}
签到签到,简单的贪心
B. Matrix of Differences
题意
给定矩阵的规模
思路
既然要让不同的差值出现,那么我们可以按照
时间复杂度:
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
nxt:while(t -- > 0){
int n = scanner.nextInt();
int[][] a = new int[n][n];
int now = 1;
boolean flag = true;
int l = 1, r = n * n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int p = i % 2 == 0 ? j : n - j - 1;
a[i][p] = flag ? l ++ : r --;
flag = !flag;
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++){
System.out.printf("%d ", a[i][j]);
}
System.out.println();
}
}
}
}
怎么赛时就是想了那么久呢…
C. Yet Another Tournament
题意
给定数组
思路
我们把这两个类型拆分成两个问题,最后合并在一起:
- 升序排序准备时间,统计能打败多少人,记为
; - 因为
,所以 的排名会更高,所以我们需要将 对应的值替换过来,否则排名会向后移一位。所以我们需要判断 在排序前数组中对应的值是否可以替换掉 在排序后数组中对应的值,如果不可以,那么将排名后移。
时间复杂度:
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t -- > 0) {
int n = scanner.nextInt(), m = scanner.nextInt();
int[] a = new int[n + 2], b = new int[n + 1];
for (int i = 1; i <= n; i++) a[i] = b[i] = scanner.nextInt();
Arrays.sort(b, 1, n + 1);
int ans = 0, sum = 0;
for (int i = 1; i <= n; i++) {
if(sum + b[i] > m) break;
sum += b[i];
ans ++;
}
if (sum + a[ans + 1] - b[ans] > m) System.out.println(n - ans + 1);
else System.out.println(Math.max(n - ans, 1));
}
}
}
题目要看清
- 本文链接 https://floating-ocean.github.io/blog_old/posts/707152960/
- 版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!