小易的英语软件
题目描述
小易需要设计一个反应同学在班上位置的软件，即“成绩超过了 p% 的同学”。
p = (分数不超过 s 的人)/ 班级总人数 * 100%
输入
第一行表示班级总人数 n
第二行有 n 个自然数，表示第 i 个同学的成绩 ai
第三行表示查询次数 q
接下来 q 行，每行一个 x，表示查询第 x 个同学的百分数 p
1 <= n, q <= 10000, 0 < ai <= 150
输出
输出应有 q 行，每行对应一次查询的结果
为了输出方便，只需要输出百分号前的数，并且保留 6 位小数(四舍五入)
样例输入
3
100 98 97
3
1
2
3
样例输出
66.666667
33.333333
0.0000000
思路
通过排序成绩 + 二分查找，快速找到 <= s 的数量
Num[<=s] == Num[< s+1]
编码
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] gradeById = new int[n]; // x = gradeById[i] => 表示同学 i 的成绩为 x
int[] gradeByAsc = new int[n]; // 成绩排序后的数组
for(int i = 0; i < n; ++i) {
gradeByAsc[i] = gradeById[i] = scn.nextInt();
}
Arrays.sort(gradeByAsc);
int q = scn.nextInt();
for(int i = 0; i < q; ++i) {
int x = scn.nextInt();
double ans;
int position = Arrays.binarySearch(gradeByAsc, gradeById[x-1]+1);
// 二分查找(同学 i 成绩 + 1)的成绩的位置，该位置-1即为小于等于该成绩的人数
if(position > 0) { // 因为可能不存在该成绩，返回 -(插入该数的位置)
ans = 1.0*(position-1)/n;
} else {
ans = 1.0*(-position-2)/n;
}
System.out.printf("%.6f\n", ans*100);
}
}
}
小易的首尾相接
题目描述
现在有 n 个数，问你是否能用这 n 个数字构成一个环(首尾相接)
同时保证任意一个数小于它相邻的2个数的和
(每个数字都必须使用并且只能用一次)
输入
第一行输入一个整数 t (1 <= t <= 10)，表示有 t 组测试用例
每个测试用例包含以下输入
第一行一个整数 n，表示数字的个数
第二行有 n 个整数 (3 <= n <= 10^5, 1 <= ai <= 10^9)
输出
应该包含 t 行，对于每组用例，若能输出“YES”，否则输出“NO”。
样例输入
1
5
17 6 17 11 17
样例输出
NO
思路
可以任意自己连接，既然出现了比较，我们就可以先排序一下
假设已经从大到小排序完毕，a0 >= a1 >= a2 >= ... >= an-1
首先取出 a0，要想让它相邻和比他大，只有让它相邻尽可能的大
那么我们将 a1、a2 放它左右(例如 a1 a0 a2 这样连接，反之亦可)
依次往后添加(如：a1 a0 a2 a3 ...)，我们会发现，在 a0 后，都可以得到 任意一个数 < 其相邻数的和(即使是 an-2 an-1 a1)
我们会发现只有 a0 是不确定的，无法直接通过排序得到 a1+a2 > a0
得到基本思路，只需要找到最大的3个数，判断 max1 < max2 + max3 即可
编码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int t = scn.nextInt();
for(int i = 0; i < t; ++i) {
int n = scn.nextInt();
int max1 = 0, max2 = 0, max3 = 0;
for(int j = 0; j < n; ++j) {
int x = scn.nextInt();
if(x > max1) {
max1 = x;
} else if(x > max2) {
max2 = x;
} else if(x > max3) {
max3 = x;
}
}
if(max2 + max3 > max1) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
小易的最小字典序
题目描述
小易给你一个包含 n 个数字的数组，执行任意次一下操作
对于任意 2 个下表 i、j，如果 ai+aj 为奇数，就可以交换
问通过任意次交换，得到字典序最小的的一组数
输入
第一行一个整数 n
第二行包含 n 个整数
(1 <= n <= 10^5，1 <= ai <= 10^9)
输出
输出字典序最小的 n 个整数(数字直接包括一个空格)
样例输入
4
7 3 5 1
样例输出
7 3 5 1
思路
// TODO
编码
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
public class Main {
private static void swap(int[] x, int a, int b) {
int t = x[a];
x[a] = x[b];
x[b] = t;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] nums = new int[n];
int[] numsByAsc = new int[n];
HashMap map = new HashMap();
for(int i = 0; i < n; ++i) {
numsByAsc[i] = nums[i] = scn.nextInt();
map.put(nums[i], i);
}
Arrays.sort(numsByAsc);
for(int i = 0; i < n; ++i) {
int position = (int) map.get(numsByAsc[i]);
for(int j = 0; j < position; ++j) {
if(nums[j] > nums[position] && (nums[j]+nums[position])%2 == 1) {
swap(nums, j, position);
map.put(nums[j], position);
map.put(nums[position], j);
break;
}
}
}
System.out.print(nums[0]);
for(int i = 1; i < n; ++i) {
System.out.print(" " + nums[i]);
}
System.out.println();
}
}
小易的查询改动个数
题目描述
小易在维护数据的时候遇到一个需求，有一个长度为 n 的序列
接下来要进行 q 次操作，每次查询输入一个 x
需要将序列种所有大于等于 x 的数减一，并输出被减一的数的个数
输入
第一行输入数字个数 n，操作次数 q
接下来一行 n 个数表示初始数字
接下来 q 行，每行一个数表示指定的数字
输出
输出每次变动的数字
思路
// TODO
编码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static void removeTag(int[] nums, int[] tags, int position) {
int num = 0;
for(int i = position; i < nums.length; ++i) {
if (tags[i] != 0) {
num += tags[i];
tags[i] = 0;
}
nums[i] -= num;
}
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt(), q = scn.nextInt();
int[] nums = new int[n];
int[] tags = new int[n];
for(int i = 0; i < n; ++i) {
nums[i] = scn.nextInt();
}
Arrays.sort(nums);
int minTagNum = nums[n-1] + 1, minTag = n;
for(int i = 0; i < q; ++i) {
int query = scn.nextInt();
int position = Arrays.binarySearch(nums, query);
if(position >= 0) {
if (minTagNum < nums[position]) {
removeTag(nums, tags, minTag);
minTagNum = nums[n - 1] + 1;
Arrays.sort(nums);
position = Arrays.binarySearch(nums, query);
} else {
++tags[position];
minTagNum = nums[position] - tags[position];
minTag = position;
}
}
if(position < 0) {
System.out.println(0);
} else {
System.out.println(n - position);
}
}
}
}