网易 牛牛找工作
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。
3 3
1 100
10 1000
1000000000 1001
9 10 1000000000
100
1000
1001
下面直接暴力，会时间超时
import java.util.*;
public class Main {
// 思路是对报酬进行排序，找到只适合的
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 工作量
final int N = in.nextInt();
// 小伙伴数量
final int M = in.nextInt();
in.nextLine();
List<long[]> inputTable = new ArrayList<>();
for(int i=0;i<N;i++){
long x = in.nextLong();
long y = in.nextInt();
inputTable.add(new long[]{x,y});
in.nextLine();
}
long[] friends = new long[M];
for(int i=0;i<M;i++){
long x = in.nextLong();
friends[i] = x;
}
Collections.sort(inputTable, new Comparator<long[]>() {
@Override
public int compare(long[] o1, long[] o2) {
int res = (int)(o2[1] - o1[1]);
return res;
}
});
for(long val:friends){
boolean flag = true;
for (long[] table:inputTable){
if(table[0] <= val){
flag = false;
System.out.println(table[1]);
break;
}
}
if(flag){
System.out.println(0);
}
}
}
}
思路采取，先按照工作难度排序，将报酬进行向后更新，保证难度大的工资高，这样就可以进行二分查找来提高查询速度，可以直接将上题改为二分查询，或者采用TreeMap
import java.util.*;
public class Main {
// 思路是对报酬进行排序，找到只适合的
// 使用TreeMap 快速找到比其大的值，减少时间复杂度
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 工作量
final int N = in.nextInt();
// 小伙伴数量
final int M = in.nextInt();
in.nextLine();
int[][] arr = new int[N][2];
for(int i=0;i<N;i++){
int x = in.nextInt();
int y = in.nextInt();
arr[i][0] = x;
arr[i][1] = y;
in.nextLine();
}
int[] friends = new int[M];
for(int i=0;i<M;i++){
int x = in.nextInt();
friends[i] = x;
}
Arrays.sort(arr,(e1,e2)->(int)(e1[0]-e2[0]));
// 将小工作难度大价值向后更新
for(int i = 1;i<arr.length;i++){
arr[i][1] = Math.max(arr[i-1][1],arr[i][1]);
}
// 将其放入TreeMap中便于查找
TreeMap<Integer,Integer> map = new TreeMap<>();
for(int i = 0; i < arr.length; i++) {
map.put(arr[i][0], arr[i][1]);
}
for(int val:friends){
Integer index = map.floorKey(val);
if(index != null) {
System.out.println(map.get(index));
} else {
System.out.println(0);
}
}
}
}
网易 被3整除
小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。
并且小Q对于能否被3整除这个性质很感兴趣。
小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。
输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。
2 5
3
思路，能被3整除的数之和可以被3整除
import java.util.*;
public class Main {
// 思路是对报酬进行排序，找到只适合的
public static void main(String[] args) {
// 生成区间数，相加为3 可以被3 整除
Scanner in = new Scanner(System.in);
long left = in.nextLong();
long right = in.nextLong();
long sum = 0;
int count = 0;
for(long i = 1;i<=right;i++){
sum += i;
if(sum % 3 == 0){
sum = 0;
if(i >= left){
count ++;
}
}
}
System.out.println(count);
}
}
网易 安置路灯
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
输入描述:
输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含'.'和'X'。
2
3
.X.
11
...XX....XX
1
3
思路：只要贪心的把每一个路灯安置在中间位置即时最优答案
import java.util.*;
public class Main {
// 安装路灯使用贪心算法遍历一遍
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while (T-- > 0){
int x = in.nextInt();
in.nextLine();
int count = 0;
char[] array = in.nextLine().toCharArray();
for(int i=0;i<array.length;i++){
if(array[i] == '.'){
count++;
i = i + 2;
}
}
System.out.println(count);
}
}
}
网易 迷路的牛牛
牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转
输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。
3
LRR
E
package com.bupt.learn;
import java.util.*;
public class Main {
// 牛牛去不可进行循环模拟即可
static String[] dirStr = {"N","E","S","W"};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
final int N = in.nextInt();
in.nextLine();
char[] arrays = in.nextLine().toCharArray();
int d = 0;
for(char c:arrays){
if(c == 'R'){
d = (d + 1) % 4;
}else if(c == 'L'){
d = (d - 1 + 4) % 4;
}
}
System.out.println(dirStr[d]);
}
}
网易 数对
牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。
输入描述:
输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。
输出描述:
对于每个测试用例, 输出一个正整数表示可能的数对数量。
5 2
7
```
直接计算时间复杂度太大
```
import java.util.*;
public class Main {
// 将规律找出并缩减计算过程
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
final int n = in.nextInt();
final int k = in.nextInt();
int count = 0;
int x = n - k;
count += (x*(x+1))/2;
for(int i = n;i>2*k;i--){
for(int j=k+1;j<=i-k;j++){
if(i / j )
if(i % j >= k){
count++;
}
}
}
System.out.println(count);
}
}
```
思路是：x % y >= k ,我们将n以内的数按照y 分成不同的区间，每一个区间内数大于k 的个数 * 区间的个数就是总大于 k 个数，因为每一个区间只是多了一个倍数，减去倍数后和第一个区间是相同的，所以可以直接按照第一个区间求解答案， 最后一个区间可能不能均分，也需要求解
```
import java.util.*;
public class Main {
// 将规律找出并缩减计算过程
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
final int n = in.nextInt();
final int k = in.nextInt();
if(k == 0){
long t = n;
System.out.println(t * t);
}else{
long count = 0;
for(int i = k;i<=n;i++){
count += (i-k)*(n / i) + Math.max(0,n%i - k + 1);
}
System.out.println(count);
}
}
}
```
网友评论