牛客网_运行问题
一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] arr = new int[n];
int sum = 0;
for (int i = 0; i < arr.length; i ++) {
arr[i] = sc.nextInt() >> 10;
sum += arr[i];
}
// dp[j]表示在容量为j的情况下可存放的重量
// 如果不放arr[i]重量为dp[j],如果放arr[i]重量为dp[j-arr[i]]+arr[i];
int[] dp = new int[sum / 2 + 1];
for (int i = 0; i < n; i ++) {
for (int j = sum / 2; j >= arr[i]; j --) {
dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
}
}
System.out.println(Math.max(dp[sum / 2], sum - dp[sum / 2]) << 10);
}
}
}
终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，Y)，小易当前在(0，0)街道，办公室在(gx,gy)街道上。小易周围有多个出租车打车点，小易赶去办公室有两种选择，一种就是走路去公司，另外一种就是走到一个出租车打车点，然后从打车点的位置坐出租车去公司。每次移动到相邻的街道(横向或者纵向)走路将会花费walkTime时间，打车将花费taxiTime时间。小易需要尽快赶到公司去，现在小易想知道他最快需要花费多少时间去公司。
import java.util.*; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int tx[] = new int[n]; int ty[] = new int[n]; for (int i = 0; i < n; i++) { tx[i] = sc.nextInt();//打车点x坐标 } for (int i = 0; i < n; i++) { ty[i] = sc.nextInt();//打车点y坐标 } int gx = sc.nextInt();//公司x坐标 int gy = sc.nextInt();//公司y坐标 int wt = sc.nextInt();// 走路速度 int dt = sc.nextInt();// 打车速度 int walkTime = (Math.abs(gx) + Math.abs(gy)) * wt;// 如果全部走路 int driveTime = Integer.MAX_VALUE; for (int i = 0; i < n; i++) {// 如果打车 driveTime = Math.min(driveTime, (Math.abs(ty[i]) + Math.abs(tx[i])) * wt + (Math.abs(ty[i]-gy)+Math.abs(tx[i]-gx)) * dt); } System.out.println(Math.min(driveTime, walkTime)); } }
在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用\’B\’表示，女生用\’G\’表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次
最终目标是将男孩移到最左边，或者将女孩移到最左边。 如果有B个男孩，则移到最左边的index分别为：0,1,2...B-1,所以所有index的和为（B-1）*B/2 一次遍历，计算目前男孩所在的index的和为sumB，则sumB减去上面的和就是所求的结果。 因此只要一次遍历，计算男孩所在的男孩的个数和男孩所在的index的和，求之差就行了。女孩同理。最后求最小值。 #include <string> #include <iostream> using namespace std; int main(){ string S; cin>>S; int B=0; int G=0; int sumB=0; int sumG=0; for(int i=0;i<S.size();i++){ if(S[i]==\'G\'){ G++; sumG+=i; } else{ B++; sumB+=i; } } int ret1=sumB-B*(B-1)/2; int ret2=sumG-G*(G-1)/2; int ret=ret1<ret2?ret1:ret2; cout<<ret; return 0; }
小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。
import java.util.*; /** * 此题巧妙地用到了List去重的方法。 * 比如说有一组数，为1 5 5 1 6 1 * 从[0,n-1]使用List去重之后，保存地其实就是每种元素最开始出现的那个元素。 * 但是我们换个角度去想，如果我们从后向前遍历，保存地就是每种元素最后出现的那个元素，只不过相对从前到后来说，数倒过来了。 * 我们最终将数反转过来即可。 * 时间复杂度为O(n) * @author 何嘉龙 * */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while(in.hasNext()) { int n = in.nextInt(); int[] arr = new int[n]; List<Integer> lists = new ArrayList<>(); for(int i = 0; i < n; i++) { arr[i] = in.nextInt(); } for(int i = n - 1; i >= 0; --i) { if(!lists.contains(arr[i])) { lists.add(arr[i]); } } for(int i = lists.size() - 1; i >= 0; --i) { System.out.print(lists.get(i)); if(i != 0) { System.out.print(" "); } } } in.close(); } }
小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。
import java.util.Scanner; //请见http://blog.csdn.net/zheng548/article/details/71075163 public class Main { /** * 利用矩阵快速幂 参考：http://www.cnblogs.com/vongang/archive/2012/04/01/2429015.html http://www.lai18.com/content/1108003.html?from=cancel */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); //用一个二维数组存储 int[][] arr= new int[1][n]; for (int i = 0; i < n; i ++) { arr[0][i] = sc.nextInt(); } //初始化单元矩阵 int[][] mul = new int[n][n]; for (int i = 0; i < n; i ++) { if (i < n - 1) { mul[i][i] = 1; mul[i + 1][i] = 1; } else { mul[i][i] = 1; mul[0][i] = 1; } } for (; k > 0; k >>= 1) { if ((k & 1) == 1) { arr = Core(arr, mul); } mul = Core(mul, mul); } int i; for (i = 0; i < n - 1; i ++) { System.out.print(arr[0][i] + " "); } System.out.println(arr[0][i]); } private static int[][] Core(int[][] a, int[][] b) { int rowRes = a.length; int columnRes = b[0].length; //TODO: int columnA = a[0].length; // == b.length; int[][] c = new int[rowRes][columnRes]; for (int i =0; i < rowRes; i ++) { for (int j = 0; j < columnRes; j ++) { for (int k = 0; k < columnA; k ++) { if (a[i][k] == 0 || b[k][j] == 0) { continue; //剪枝 } c[i][j] += a[i][k] * b[k][j]; } //100取余运算 if (c[i][j] >= 100) { c[i][j] %= 100; } } } return c; } }
现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。
//利用回溯法求解. //题意有两个地方没说清楚：1、一个人只能做一项工程，而不能分饰两角； // 2、有几个工程师，每个工程师有一个工作即满足题意，不用6项工作全部都要有人做。 //前一个人选了哪项工作，直接影响后一个人的选择余地。 //所以需要用一个set记录在当前这个人选择之前，前面那些人已经选了的工作，进而他只能选除set中已有剩下的工作。 //当考察完最后一个人，情况数+1（递归出口），证明是满足题意的方案。下面是代码 import java.util.HashSet; import java.util.Scanner; //网易：工程师与项目的匹配 public class Wangyi_WorkAndWorker { private static int cases = 0; public static void main(String[] args) { //读取输入 Scanner in = new Scanner(System.in); int n = in.nextInt(); String[] ables = new String[n]; for(int i = 0; i < n; i++) ables[i] = in.next(); //计算 backtracing(ables, 0, new HashSet<Integer>()); System.out.println(cases); in.close(); } public static void backtracing(String[] ables, int index, HashSet<Integer> set){ if(index >= ables.length){ cases++; return; } String able = ables[index]; for(int i = 0; i < able.length(); i++){ int work = able.charAt(i) - \'0\'; if(!set.contains(work)) { set.add(work); backtracing(ables, index + 1, set); set.remove(work); } } } }
小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性.
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。
链接：https://www.nowcoder.com/questionTerminal/df51567da86c456bb962ad58d91804ca 来源：牛客网 import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String args[]){ Scanner myscanner=new Scanner(System.in); int w=myscanner.nextInt(); int x=myscanner.nextInt(); int y=myscanner.nextInt(); int z=myscanner.nextInt(); myscanner.close(); float p=0; Set mySet=new HashSet(); for(float i=w;i<=x;i++){ for(float j=y;j<=z;j++){ p=i/j; mySet.add(Float.toString(p)); } } System.out.println(mySet.size()); } }
常规的表达式求值，我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易所在的世界没有除法，意味着表达式中没有/，只有(+, – 和 *)。现在给出一个表达式，需要你帮忙计算出小易所在的世界这个表达式的值为多少
链接：https://www.nowcoder.com/questionTerminal/5f2186b48691435388ceccc1269e212a 来源：牛客网 package expression; import java.util.*; /** * 3+5*7 * 先来看这道题的解题步骤： * 1. 当遇到数字3的时候，设置一个变量cur记录下它； * 2. 当遇到\'+\'时，判断flag的状态，根据flag的状态去更新res。例如，我们设置默认的flag为\'+\'，故res+=cur，得到res=3， * 并且更新flag的状态为当前的字符\'+\'; * 3. 又遇到数字5，更新cur的值为5； * 4. 遇到符号\'*\'，执行步骤2，根据flag的状态去更新res。由于我们之前的flag为\'+\'，故res+=cur,为3+5=8，得到res=8， * 并且更新flag的状态为当前的字符\'*\'; * 5. 遇到数字7，更新cur的值为7； * 6. 这时候已经到了表达式的最后了，也执行步骤2，故可以得到res=8*7=56。 * 这道题的难点就在于： * 第一个数是负数怎么处理？-3+5*7 * 可以看到代码中，当第一个数为负数的时候，则第一个字符为\'-\',故flag的状态更新为了\'-\'。 * 再遇到3的时候，更新cur的值为3,再遇到字符\'+\',先根据flag的状态执行res-=cur，得到res=-3. * 后面步骤的就跟之前的一样了。 * @author 何嘉龙 * */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { String str = in.nextLine(); int res = getExpressionVal(str); System.out.println(res); } in.close(); } public static int getExpressionVal(String str) { char[] chas = str.toCharArray(); int res = 0; int cur = 0; char flag = \'+\'; for (int i = 0; i < chas.length; i++) { if (chas[i] < \'0\' || chas[i] > \'9\' || i == chas.length - 1) { if (i == chas.length - 1) { cur = chas[i] - \'0\'; } if (flag == \'+\') { res += cur; } else if (flag == \'-\') { res -= cur; } else { res *= cur; } flag = chas[i]; } else { cur = chas[i] - \'0\'; } } return res; } }
小易有一块n*n的棋盘，棋盘的每一个格子都为黑色或者白色，小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画，帮助小易算算他会涂画多少个棋格。
import java.util.Scanner; /* * 这题就是求各数组相同字符子串的最大长度 * */ public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); while (scan.hasNext()) { int n = scan.nextInt(); String[] str = new String[n]; for (int i = 0; i < n; i++) { str[i] = scan.next(); } int count = 0; for (int j = 0; j < n; j++) { int c = 1; for (int i = 0; i < n - 1; i++) { if (str[i].charAt(j) == str[i + 1].charAt(j)) { c++; count = Math.max(c, count); } else { c = 1; } } } System.out.println(count); } scan.close(); } }
小易参与了一个记单词的小游戏。游戏开始系统提供了m个不同的单词，小易记忆一段时间之后需要在纸上写出他记住的单词。小易一共写出了n个他能记住的单词，如果小易写出的单词是在系统提供的，将获得这个单词长度的平方的分数。注意小易写出的单词可能重复，但是对于每个正确的单词只能计分一次。
package english;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
int n = in.nextInt();
int m = in.nextInt();
List<String> systemWords = new ArrayList<>();
Set<String> writeWordsSet = new HashSet<>();
List<String> writeWordsList = new ArrayList<String>();
for(int i = 0; i < n; i++) {
systemWords.add(in.next());
}
for(int i = 0; i < m; i++) {
String str = in.next();
if(systemWords.contains(str)) {
writeWordsSet.add(str);
}
}
writeWordsList.addAll(writeWordsSet);
int sum = 0;
for(int i = 0; i < writeWordsList.size(); i++) {
int len = writeWordsList.get(i).length();
sum += Math.pow(len, 2);
}
System.out.println(sum);
}
in.close();
}
}
小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。
借鉴前面几位大神的代码，分析都写在代码中 import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] h = new int[n]; int sum = 0; for (int i = 0; i < n; i++) { h[i] = in.nextInt(); sum += h[i]; } //本来想用二维数组来存放，但运行会超出内存，所以行不通 int[] dp0 = new int[sum * 2 + 1], dp1 = new int[sum * 2 + 1]; //dp0表示上次放砖时各个位置的情况，dp1表示这次放砖时应该变成的情况 //dp平移sum位是因为B堆-A堆高度的范围在-sum至sum之间，所以平移sum位以便存储每个的值 //所以也就是说j下标为sum时表示A、B堆高度相同时的情况，往左就是B堆较高的情况，往右就是A堆较高的情况 for (int i = 0; i < sum*2 + 1; i++) dp0[i] = -1; dp0[sum] = 0; for (int i = 1; i <= n; i++) { int hg = h[i-1]; //j表示B堆-A堆的高度差（由于平移的原因，sum即为0，往左一次加1，往右依次减1） //dp1[j]存放的值表示B目前所能存放的最大高度 //dp1[j]是在上次的基础上（也就是dp0）进行变换的 for (int j = 0; j < 2 * sum + 1; j++) { dp1[j] = dp0[j]; if (j - hg >= 0 && dp0[j - hg] != -1) { dp1[j] = Math.max(dp0[j - hg], dp1[j]); } if (j + hg <= 2 * sum && dp0[j + hg] != -1) { dp1[j] = Math.max(dp0[j + hg] + hg, dp1[j]); } } //交换两个数组，确保dp0一直是上次的状态 int[] t = dp0; dp0 = dp1; dp1 = t; } //最后一次变换完为dp0，所以对dp0进行求解 if (dp0[sum] == 0) System.out.println(-1); else System.out.println(dp0[sum]); } }
易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值
### 分析 显然数字太大我们不能直接计算模(超过long long)，而且也不能枚举X(否则空间可能有$10^{18}$)。不过我们考虑到模n应该不大（喂喂，怎么题目没有给n的范围啊～），因此可以考虑用动态规划的思想从这里入手。 用$mod[k]$表示当前所有情况下模n余k的数量。如果我们把前i位当成一个整体$s[0:i]$，而且知道了$mod[0:n]$的值，那么对于前i+1位而言，$mod[k]$的值会贡献到$mod[(k*10+s[i+1])mod\\%n]$上。如果$s[i+1]$的值是X，那么我们只要将$s[i+1]$遍历10次。 总体上说，就是从前往后遍历，依次更新mod数组，最后的结果当然就是$mod[0]$了。 注意long long 。 ### 我的答案 ```cpp #include<iostream> #include<cstring> using namespace std; #define MAXN 100000 void transform1(long long mod[],int n){ long long tmpMod[MAXN]={0}; for(int i=0;i<n;i++){ for(int j=0;j<10;j++){ tmpMod[(i*10+j)%n]+=mod[i]; } } memcpy(mod,tmpMod,sizeof tmpMod); } void transform2(long long mod[],int k,int n){ long long tmpMod[MAXN]={0}; for(int i=0;i<n;i++){ tmpMod[(i*10+k)%n]+=mod[i]; } memcpy(mod,tmpMod,sizeof tmpMod); } int main(){ long long mod[MAXN]={0}; string s; int n; cin>>s>>n; mod[0]=1; for(int i=0;i<s.length();i++){ if(s[i]==\'X\'){ transform1(mod,n); }else{ transform2(mod,s[i]-\'0\',n); } } cout<<mod[0]<<endl; } ```
版权声明：本文为xf666原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。