三角形_猴子分桃_mkdir
三角形
在线OJ注意输入输出 格式和范围!
这里的范围超过了 int和long的大小!!!
所以我们要通过字符串或者BigInteger进行计算!
BigInteger类
表示范围: -2 ^Integer.MAX_VALUE （排他） ~ +2 ^ Integer.MAX_VALUE （排他）
包名:java.math.BigInteger
BigDecimal类 对应更大精度的浮点型(超过16位)计算!!!
第2个构造方***导致double的精度丢失!
import java.util.*;
import java.math.BigInteger;//导入包 java.math!!!
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
BigInteger[] arr = new BigInteger[3];
for(int i = 0;i<arr.length;i++){
arr[i] = sc.nextBigInteger();
}
Arrays.sort(arr);
//注意:BigInteger 不可以直接相加,要使用 add 方法进行相加!
//通过 compareTo方法进行比较!
//arr[0]+arr[1]>arr[2] error!!!
if(arr[0].add(arr[1]).compareTo(arr[2])>0){
//两边之和大于第三边
System.out.println("Yes");
}else{
System.out.println("No");
}
}
}
} 猴子分桃
链接：https://www.nowcoder.com/questionTerminal/480d2b484e1f43af8ea8434770811b4a
来源：牛客网
题目分析:
从题目中来看，小猴子每次将桃子均分为 5 堆时都会多出来 1 个，所以为了方便计算，我们在最开始时就借给猴子们 4 个桃子，这样的话，每次都可以刚好均分为 5 堆!
假设在开始时就有
X个桃子，借给猴子们4个后，此时就一共有X+4个桃子。
当第一只小猴子来时，它将X+4个桃子均分为 5 堆后，拿走(X+4)*(1/5)个，剩余(X+4)*(4/5)个桃子。在这里，有人可能会有疑问：给老猴子的那个桃子去哪里呢？其实，小猴子拿的那一部分就包括了这一个桃子，并且小猴子也没有多得桃子，它实际上得到的桃子数为(X+4)*(1/5) - 1 = (X-1)*(1/5)，这和在不借给它们 4 个桃子的情况下得到的数量是一样的，不过此时剩余的桃子数相较于之前多了(X+4)*(4/5) - (X-1)*(4/5) = 4个，但这样就恰巧保证了下一只小猴子分桃时，也能刚好均分为 5 堆。由此可见，所有的小猴子都不会多得桃子，老猴子也不会少得桃子，并且每次小猴子都能刚好将桃子均分为 5 堆，而借给的那 4 个桃子每次都在剩余的那部分里，最后去除即可。
当第二只小猴子来时，它将(X+4)*(4/5)个桃子均分为 5 堆后，拿走(X+4)*(4/5)*(1/5)个，剩余(X+4)*(4/5)^2个桃子。
当第三只小猴子来时，它将(X+4)*(4/5)^2个桃子均分为 5 堆后，拿走(X+4)*(4/5)^2*(1/5)个，剩余(X+4)*(4/5)^3个桃子。
.....
依次类推，当第 n 只小猴子（最后一只小猴子）来时，它将(X+4)*(4/5)^(n-1)个桃子均分为 5 堆后，拿走(X+4)*(4/5)^(n-1)*(1/5)个，剩余(X+4)*(4/5)^n个桃子。
为了满足题目最后的要求，也就是要保证最后剩余的桃子数最少且为整数，那么当 X+4 = 5^n 时，刚好满足要求，此时可得出：
（1）开始时的总桃子数：X = 5^n - 4
（2）老猴子最后能得到的桃子数：n + (X+4)*(4/5)^n - 4 = n + 4^n - 4
因为老猴子能得到的桃子主要有两个来源：一是每个小猴子都要给一个，有 n 只小猴子，就可以得到 n 个；二是最后剩余的桃子都归老猴子所有，从上面最后一次的结果来看，一共剩余了 (X+4)*(4/5)^n 个桃子，但是这里面包括我们最早借给它们的 4 个，实际上剩余的桃子数为 (X+4)*(4/5)^n - 4 ，所以最后总共能得到的桃子数就是 n + (X+4)*(4/5)^n - 4 。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = 0;
while(sc.hasNext()){
n = sc.nextInt();
if(n == 0)
break;
long a = (long)Math.pow(5, n); //5^n
long b = (long)Math.pow(4, n);//4^n
//a 最小需要桃子数 5^n-4 (X - 4)(减去借的4个桃子)
//b 老猴子 分到的 n + (X+4)*(4/5)^n - 4 = n + 4^n - 4
System.out.println((a-4)+" "+(b-4+n));
}
}
} mkdir
//方法一:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
String[] arr = new String[n];
for (int i = 0; i < arr.length; i ++ ) {
arr[i] = sc.next();
}
Arrays.sort(arr);
List<String> res = new ArrayList<>();
for (int i = 1; i < arr.length; i ++ ) {
if( ! arr[i].startsWith(arr[i - 1] + "/")) res.add(arr[i - 1]);
}
res.add(arr[n - 1]);
for (String s:res) {
System.out.println("mkdir -p " + s);
}
System.out.println();
}
}
}
//方法二:伪删除!
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
String[] arr = new String[n];
for (int i = 0; i < arr.length; i ++ ) {
arr[i] = sc.next();
}
Arrays.sort(arr);
boolean[] flg = new boolean[n];
//伪删除
for(int i = 0;i<n-1;i++){
if(arr[i].equals(arr[i+1])){
//相等保留一个!
flg[i] = true;
}else if(arr[i].length()<arr[i+1].length()&&arr[i+1].contains(arr[i])&&arr[i+1].charAt(arr[i].length())=='/'){
flg[i] = true;
}
}
for (int i=0;i<n;i++) {
if(!flg[i])
System.out.println("mkdir -p " + arr[i]);
}
System.out.println();
}
}
} 
投递滴滴等公司9个岗位 >