今日刷三题（day4）：简写单词+dd爱框框+除2！

题目一：简写单词

题目描述：

比如 “College English Test”可以简写成“CET”，“Computer Science”可以简写为“CS”，“I am Bob”简写为“IAB”

输入输出描述：
输入：一个复合单词

输出：输出一行，表示复合词的简写

思路解析：

step 1：输入一个字符串数组，规定以空格符号隔开
step 2：标记数组中每一组的第一个字母为ch
step 3：如果ch>=‘a’&&ch<='z',则转化为大写

作答情况（正确）：

字符转化为大写的函数要掌握。

代码：

 public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] s = sc.nextLine().split(" ");StringBuffer sb = new StringBuffer();for (int i = 0; i < s.length; i++) {char ch=s[i].charAt(0);if(ch>='a'&&ch<='z'){ch=Character.toUpperCase(ch);}sb.append(ch);}System.out.print(sb);}

题目二：dd爱框框

题目描述：

读入n，x,给出n个数a[1],a[2],……,a[n]，求最小的区间[l,r]，使a[l]+a[l+1]+……+a[r]≥x，若存在相同长度区间，输出l最小的那个。

输入输出描述：
输入：第一行两个数(1≤n≤10000000),x(1≤x≤10000)

输出：第二行n个数a[i](1≤a[i]≤1000)

思路解析：

同相双指针/滑动窗口

step 1（进窗口）：sum+=arr[right]
step 2(判断)：sum>=x?
step 3(更新结果)：(right-left+1<retlen)?

step 4(出窗口)：sum-=arr[left]

作答情况（运行超时）：

①如果使用简单的Scanner&&System.out是从IO设备中读入，每次读取性能开销较大，在写代码时会造成超时的情况。

②对这个判断加上循环，可以减少内存和时间开销。

代码：

import java.io.*;
import java.util.*;
public class Main{static class Read {//字符串裁剪StringTokenizer st = new StringTokenizer("");/*  Java 处理IO有两套标准：①字节流（System.in）②字符流（含有Reader、Writer的）*///下面这一行两个作用：// （1）把输入的字节流（System.in）转化为点电脑可识别的字符流new InputStreamReader（）//（2）BufferedReader 相当于一个内存缓冲区（读取数据快、稳）BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException {//下面这一行有两个作用：//（1）while循环相当于多组输入的情况//（2）new StringTokenizer(bf.readLine())按行裁剪while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}//读取裁剪后一行中的一个字符串return st.nextToken();}String nextLine() throws IOException {return bf.readLine();}int nextInt() throws IOException {return Integer.parseInt(next());}long nextLong() throws IOException {return Long.parseLong(next());}double nextDouble() throws IOException {return Double.parseDouble(next());}}public static Read in = new Read();public static void main(String[] args) throws IOException {int n=in.nextInt();int x=in.nextInt();int[] arr=new int[n+1];for(int i=1;i<arr.length;i++){arr[i]=in.nextInt();}int sum=0;int left=1;int right=1;int retLen=0x3f3f3f3f;//系统最大值int retLeft=-1;int retRight=-1;//step 1（进窗口）：sum+=arr[right] while(right<=n){sum+=arr[right];//step 2(判断)：sum>=x?while(sum>=x){//step 3(更新结果)：(right-left+1<retlen)?if(right-left+1<retLen){ retLeft=left;retRight=right;retLen=right-left+1;}   //step 4(出窗口)：sum-=arr[left]sum-=arr[left];left++;}right++;}System.out.print(retLeft+" "+retRight);}
}

题目三：除2！

题目描述：

给一个数组，一共有 n 个数。你能进行最多 k 次操作。每次操作可以进行以下步骤：
选择数组中的一个偶数啊a[i],将其变成a[i]/2 现在你进行不超过 k次操作后，让数组中所有数之和尽可能小。请输出这个最小的和。

输入输出描述：

输入：第一行输入两个正整数 n 和 k ，用空格隔开；第二行输入 n 个正整数 ai

数据范围：1 ≤ n≤100000，1≤k≤10^9 1≤ai≤10^9

输出描述:
一个正整数，代表和的最小值。

思路解析：

大堆（每次选出最大的偶数）+贪心

作答情况（未作出）：

①未想到大根堆解法；②sum根据输入描述必须用long

代码：

import java.io.*;
import java.util.*;
public class Main{public static Read in = new Read();static class Read {//字符串裁剪StringTokenizer st = new StringTokenizer("");/*  Java 处理IO有两套标准：①字节流（System.in）②字符流（含有Reader、Writer的）*///下面这一行两个作用：// （1）把输入的字节流（System.in）转化为点电脑可识别的字符流new InputStreamReader（）//（2）BufferedReader 相当于一个内存缓冲区（读取数据快、稳）BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException {//下面这一行有两个作用：//（1）while循环相当于多组输入的情况//（2）new StringTokenizer(bf.readLine())按行裁剪while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}//读取裁剪后一行中的一个字符串return st.nextToken();}String nextLine() throws IOException {return bf.readLine();}int nextInt() throws IOException {return Integer.parseInt(next());}long nextLong() throws IOException {return Long.parseLong(next());}double nextDouble() throws IOException {return Double.parseDouble(next());}}public static void main(String[] args) throws IOException {int n=in.nextInt();int k=in.nextInt();PriorityQueue<Integer> queue=new PriorityQueue<>((o1,o2)->o2-o1);long sum=0; long x=0;for(int i=0;i<n;i++){x=in.nextLong(); sum+=x;//35if(x%2==0){
queue.add((int)x);}}while(!queue.isEmpty()&&k!=0){long t=queue.poll()/2;sum-=t;//35-5-4-2k--;if(t%2==0){queue.add((int)t);}
}System.out.print(sum);}
}

收获：

①字符大小写的转换

小写字符/字符串转化为大写字符的函数：

         //字符Character ch='a';ch=Character.toUpperCase(ch);//字符串String str="HELLO";str=str.toUpperCase();

大写字符转化为小写字符的函数：

          //字符Character ch='a';ch=Character.toLowerCase(ch);//字符串String str="HELLO";str=str.toLowerCase();

②Scanner输入会导致超时，这里给了大家一个输入模板，请大家跳转到这条博客Java输入输出模板( 针对ACM模式)-CSDN博客