牛客题解

文章目录

day4_17
- - **BC149** **简写单词**
  - - - 思路：模拟
      - 代码：
  - dd爱框框
  - - - 思路：滑动窗口（同向双指针）
      - 代码：
  - 除2！
  - - - 思路：模拟+贪心+堆
      - 代码：

day4_17

BC149 简写单词

https://www.nowcoder.com/practice/0cfa856bf0d649b88f6260d878f35bb4?tpId=290&tqId=39937&ru=/exam/oj

思路：模拟

代码：

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            char c = in.next().charAt(0);
            if(c>='a'&&c<='z'){
                System.out.print((char)(c-32));
            }else{
                System.out.print(c);
            }
        }
    }

dd爱框框

https://ac.nowcoder.com/acm/contest/11211/F

在这里插入图片描述

思路：滑动窗口（同向双指针）

1.从1开始计数的

2.区间内的数字必须严格大于0，因为如果区间中存在小于0的数，left在滑动的时候，可能会增大，会倒逼right回退。只有严格大于0的数，随着left滑动，区间之和才会减小。right就会向后移动。

进窗口：sum += arr[right]
判断条件:sum >=x
更新结果：right-left+1 < retlen retleft = left, retright = right
出窗口：sum-= arr[left]

代码：

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args )throws IOException{
        Read in = new Read();
        int n = in.nextInt(),x = in.nextInt();
        int[]arr = new int[n+1];
        for(int i = 1; i<=n ; i++){
            arr[i] = in.nextInt();
        }
        int left = 1,right = 1,sum = 0;
        int retleft = -1,retright = -1,retlen = n;
        while(right<=n){
            //进窗口
            sum += arr[right];
            while(sum>=x){
                //更新结果
                if(right-left+1 < retlen){
                    retleft = left;
                    retright = right;
                    retlen = right-left+1;
                }
                sum -= arr[left++];//出窗口
            }
            right++;
        }
        System.out.println(retleft+" "+retright);  
    }
}
class Read{
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String next()throws IOException{
        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());
    }
}

除2！

https://ac.nowcoder.com/acm/contest/8563/A

在这里插入图片描述

思路：模拟+贪心+堆

1.优先级队列确保出队的都是最大值

2.如果出队/2之后仍是偶数，再次进队。

代码：

import java.util.*;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b)->{
            return b-a;
        });
        long sum = 0,x;
        for(int i = 0; i<n; i++){
            x = in.nextLong();
            sum += x;
            if(x%2 == 0){
                heap.add((int)x);
            }
        }
        while(k-- != 0 && !heap.isEmpty()){
            long t = heap.poll() / 2;
            sum -= t;
            if(t%2 == 0){
                heap.add((int)t);
            }
        }
        System.out.println(sum);
    }
}