练习1--翻硬币
1)题目及要求
2)解题思路
输入的是字符串,要想将两组字符串进行一一对比,需要将字符串转换成字符数组,再使用for循环依次遍历字符数组,进行比对。
输入两行字符串,转换成两个字符数组;将初始数组和目标数组进行逐个对比,运用三目运算符进行判断
3)详细代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
String origin=scan.next();
String target=scan.next();
char[] originLine=origin.toCharArray();
char[] targetLine=target.toCharArray();
int result=0;
for(int i=0;i if(originLine[i]!=targetLine[i]){ originLine[i]=originLine[i]== '*'?'o':'*'; originLine[i+1]=originLine[i+1]== '*'?'o':'*'; result++; } } scan.close(); System.out.println(result); } } 4)本题核心 if(originLine[i]!=targetLine[i]){ originLine[i]=originLine[i]== '*'?'o':'*'; originLine[i+1]=originLine[i+1]== '*'?'o':'*'; result++; } 练习2--付账 1)题目及要求 2)解题思路 让每个人尽可能付接近平均金额的钱数 根据金额和人数计算平均金额;对每个人的钱数进行从小到大排序;遍历排序后,将钱数少于平均金额的人 全部支付,再从总金额里减去该人所支付的金额;重新计算平均金额,剩余金额/剩余人数,同样钱数少于新平均金额的人也全部支付;最后钱最多的人支付剩余的。以此类推 3)详细代码 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; /** * 贪心:为了使得标准差最小,每一个出的钱bi必须接近平均值s/n * [1]第i个人带的钱不够平均数avg,那么他只能出自己全部的钱ai * [2]第i个人带的钱比平均数avg多,那么他可以多付一些。 * * 基本步骤如下: * 1、对ai从小到大排序 * 2、排序后前一部分人的钱不够,那么就出他们所有的钱 * 3、从总付钱数中扣除前一部分人出的钱,得剩余需要出得钱数为S', * 以及剩余得后一部分人的出钱平均数avg' * 4、后一部分人的钱多,他们多出一些: * (1)比较有钱的,但是他的钱也不够avg',那么他的钱也是全部出 * (2)非常有钱的,不管怎么付他都有富余 */ public class Main { public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static void main(String[] args) throws IOException { int n = nextInt(); long s = nextLong(); long[] a = new long[n]; //每个人带的钱数 for (int i = 0; i a[i]=nextLong(); } //开始贪心选择 Arrays.sort(a);//排序,从小到大 double avg=1.0*s/n; double sum=0; for (int i = 0; i if(a[i]*(n-i) sum+=(a[i]-avg)*(a[i]-avg); s-=a[i]; //更新还差多少钱 }else{ //不需要把钱全部拿出的人。剩下的人中,钱最少的人都可以达到cur_avg double cur_avg=1.0*s/(n-i);//注意这里的s是还差多少钱 //如果这个人有钱付,那么后面的人一定也能付,所以直接乘后面的人数(n - i)即可 sum+=(cur_avg-avg)*(cur_avg-avg)*(n-i); break; } } System.out.printf("%.4f",Math.sqrt(sum/n)); } public static int nextInt() throws IOException{ st.nextToken(); return (int)st.nval; } public static long nextLong() throws IOException{ st.nextToken(); return (long)st.nval; } } 4)本题核心 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Scanner scanner = new Scanner(br); int n = scanner.nextInt(); long s = scanner.nextLong(); long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextLong(); } // ... (其余代码逻辑保持不变) } } 输入和初始化: 通过StreamTokenizer和BufferedReader从标准输入读取数据。nextInt()和nextLong()方法用于读取整数和长整数。初始化变量n(人数)、s(总金额需求)和a数组(每个人持有的钱)。 排序: 使用Arrays.sort(a)对a数组进行排序,以确保从小到大的顺序。这是贪心策略的一部分,因为我们希望先使用钱较少的人来尽量接近平均值。 计算平均值: 计算总需求s的平均值avg。 贪心选择: 遍历排序后的a数组。对于每个人,我们检查他们是否有足够的钱来支付平均值。 如果某人的钱不足以支付平均值(即a[i] * (n - i) < s),那么他们会把所有的钱都拿出来。此时,我们更新总需求s,并计算这个人与平均值的差的平方,累加到sum中。如果某人的钱足够支付平均值,那么他们会支付平均值的金额,而后面的所有人也都能至少支付这个金额。因此,我们计算当前平均值与总平均值的差的平方,并乘以剩余的人数(n - i),然后累加到sum中。之后,我们跳出循环,因为没有必要再检查后面的人。 计算标准差: 使用公式Math.sqrt(sum / n)计算标准差,并保留四位小数后输出。这里,sum是每个人与平均值的差的平方的总和,而n是人数。标准差是衡量这组数分布离散程度的指标。 相关文章
发表评论