【Java】贪心专题训练

文章目录

题目链接知识汇总题目列表

快输模板A - 外币兑换B - 删数问题C - 股票买卖D - 数列分段E - 最大子段和F - 活动安排问题G - 线段H - 定价I - 排队接水J - 拼成最小的数 V2K - Huffman coding treeL - 货币系统M - 反素数antN - 接水问题二

题目链接

HENAU冬令营-贪心专题
密码：202202100000

知识汇总

贪心/动归/搜索的区别
从零开始学贪心算法

题目列表

快输模板

import java.io.*;
import java.util.*;
import java.util.regex.*;
public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        boolean hasNext() {
            if (st != null && st.hasMoreTokens())
                return true;
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                return false;
            }
            return true;
        }
    }

    static PrintWriter out = new PrintWriter(
            new BufferedWriter(new OutputStreamWriter(System.out)));
    
}

A - 外币兑换

找最大汇率，美金数量*汇率即得所获人民币最大值。

	public static void main(String[] args) {
        FastReader sc = new FastReader();
        double n=sc.nextDouble();
        double a[]=new double[12];
        double max=0;
        for(int i=0;i<12;i++){
            a[i]=sc.nextDouble();
            if(a[i]>max)max=a[i];
        }
        out.printf("%.2f",max*n);
        out.flush();
    }

B - 删数问题

每次都取出第一个升序数列的末尾数字，直至取够指定次数。
注意：输出时需要判断第一位是否为0，结果不含前导0。
解法参考：删数问题

	public static void main(String[] args) {
        FastReader sc = new FastReader();
        char c[]=(sc.next()).toCharArray();
        int k=sc.nextInt(),i;
        int len=c.length;
        while(k!=0) {
            i=0;//下标，循环求升序数列的最后一个值
            while(i 
 
C - 股票买卖 
 
 状态转移方程：dp[i]=Math.max(dp[i-1],a[i]-min[i])； 
  
  dp[i]:以第i个数为节点的最大利润
 min[i]:第i个数前的最小值 
  
 解法参考： 股票买卖 
 
	static int a[],minl[],maxr[],dp1[],dp2[];
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int t=sc.nextInt();
        int n;
        while(t-->0){
            n=sc.nextInt();
            ini(n);//初始化数组
            for(int i=1;i<=n;i++)a[i]=sc.nextInt();
            minl[1]=a[1];
            dp1[1]=0;
            for(int i=2;i<=n;i++)
            {
                minl[i]=Math.min(minl[i-1],a[i]);//找到这个数之前的最小值
                dp1[i]=Math.max(dp1[i-1],a[i]-minl[i]);//求出以这个数为节点的最大利润
            }
            maxr[n]=a[n];
            dp2[n]=0;
            for(int i=n-1;i>=1;i--)
            {
                maxr[i]=Math.max(maxr[i+1],a[i]);//找到这个数之后的最大值
                dp2[i]=Math.max(dp2[i+1],maxr[i]-a[i]);//求出以这个数为节点的最大利润
            }
            int ans=-1061109567;
            //保证所找两个值不重复
            for(int i=1;i<=n;i++)ans=Math.max(ans,dp1[i]+dp2[i]);
            out.printf("%dn",ans);
        }
        out.flush();
    }
    public static void ini(int n){
        a=new int[n+1];
        minl=new int[n+1];
        maxr=new int[n+1];
        dp1=new int[n+1];
        dp2=new int[n+1];
    }
 
 
D - 数列分段 
 
 当前和大于最大子段和，分段数+1，当前和初始化为当前数字 
 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n=sc.nextInt();//数组长度
        int m=sc.nextInt();//最大子段和
        int a[]=new int[n];
        int cursum=0,count=1;
        for(int i=0;im){
                count++;
                cursum=a[i];
            }
        }
        out.println(count);
        out.flush();
    }
 
 
E - 最大子段和 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n=sc.nextInt();
        int num[]=new int[n+1];
        for(int i=0;i0&&dp[i-1]>0)
                dp[i]=dp[i-1]+num[i];
            else
                dp[i]=num[i];
        long max=0;
        for(int i=0;i 
 
F - 活动安排问题 
 
 解法参考：51nod 1428 
 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n=sc.nextInt();
        int s[]=new int[n];
        int e[]=new int[n];
        int i,k;
        for(i=0;i 
 
G - 线段 
 
 贪心策略为，优先保留结尾小且不相交的区间。在选择要保留的区间时，选择的区间结尾越小，余留给其他区间的空间就越大，就越能保留更多区间。 
 解法参考：Java版 视频6:25-13:30 & C++版 
 
 
 Java 得分70.0/100.0（TLE） 
 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n=sc.nextInt();
        int line[][]=new int[n][2];
        for(int i=0;i() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        int sum=1;
        int pre=line[0][1];
        for(int i=1;i 
 
 C++ 得分100.0/100.0 （AC） 
 
#include
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef pair Pair;

const int N=1e6+5;
int n,i;
Pair p[N];
bool cmp(Pair a,Pair b)
{
    return a.second>n){
        for(i=0;i>p[i].first>>p[i].second;
        }
        sort(p,p+n,cmp);
        int pre=p[0].second,ans=1;
        for(i=1;i 
 
H - 定价 
 
 重点在于优化枚举过程，某一区间内算得荒谬度最小值相同，而区间的判断与末尾0的个数有关。
 解法参考： BZOJ4029-定价 
 
	
    static int cnt[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int T=sc.nextInt();
        int l,r;
        while(T-->0) {
            l=sc.nextInt();
            r=sc.nextInt();
            int ans=0,min=20;
            for(int i=l;i<=r;i+=cnt[getInterval(i)]) {
                //结尾是5，荒谬度为2*a-1；否则为2*a
                int degree=2*getDigit(i)-getLast(i);
                if(min>degree) {
                    min=degree;
                    ans=i;
                }
            }
            out.println(ans);
        }
        out.flush();
    }
    //针对cnt[]数组求下标。即是末尾0的个数。
    public static int getInterval(int x){
        int i=0;
        while (x%10==0){
            x/=10;
            i++;
        }
        return i;
    }
    //求一个数的最后一位非零数的值。如果是5，则返回1，否则返回0。
    public static int getLast(int x){
        while(x%10==0)x/=10;
        int tp=x%10;
        if(tp==5)return 1;
        else return 0;
    }
    //求一个数不含末尾0的位数
    public static int getDigit(int x){
        int sum=0;
        while(x%10==0)x/=10;
        while(x!=0){
            x/=10;sum++;
        }
        return sum;
    }
 
 
I - 排队接水 
 
 当前所有人等待时间=当前接水时间*当前人数总和。
 即排队时，越靠近前面的计算次数越多，因此越小的排在越前面得出的结果越小。 
 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n=sc.nextInt();
        int t[]=new int[n];
        for(int i=0;i 
 
J - 拼成最小的数 V2 
 
 任意两个字符串（将数字转为字符串）a和b，根据a+b和b+a的字典序进行比较。字典序较小则排在前面。
 解法参考：51nod 2986 
 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n=sc.nextInt();
        Integer id[]=new Integer[n];
        String s[]=new String[n];
        for(int i=0;i() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return (s[o1]+s[o2]).compareTo(s[o2]+s[o1]);
            }
        });
        for(int i=0;i 
 
K - Huffman coding tree 
 
 题意 - 输出哈夫曼树的WPL（带权路径长度）
 题目翻译：OpenJudge - Huffman编码树
 解法参考：哈夫曼树的WPL值的计算
 即WPL=（哈夫曼树）非叶子节点值之和 
 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n=sc.nextInt();
        PriorityQueue pq=new PriorityQueue<>
                (new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;//升序排列
            }
        });
        int w,wpl=0;
        for(int i=0;i=2){
            a=pq.poll();
            b=pq.poll();
            tp=a+b;
            wpl+=tp;
            pq.add(tp);
        }
        out.println(wpl);
        out.flush();
    }
 
 
L - 货币系统 
 
 为满足 (m,b) 与原来的货币系统 (n,a) 等价，则面额数组b是面额数组a的子数组；为使m 尽可能的小，则应使面额数组b中的任意元素不能被其他元素所表示。
 题目链接：AcWing 532. 货币系统
 解法参考：货币系统（完全背包问题） 
 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int T=sc.nextInt();
        int n,ans;
        int num[],dp[];
        while(T-->0){
            ans=0;
            n=sc.nextInt();
            num=new int[n];
            for(int i=0;i 
 
M - 反素数ant 
 
 解法参考：反素数ant(唯一分解定理的应用) 
 
	//不超过N的最大的反质数:约数个数最多的数中的最小值
    static int n,ps[]={2,3,5,7,11,13,17,19,23,29,31},min,sum;
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        n=sc.nextInt();
        dfs(0,30,1,1);
        out.println(min);
        out.flush();
    }
    //idx引用质因子数组下标，limit限制当前因子的个数，cur表示当前数字，s表示约数个数
    public static void dfs(int idx,int limit,int cur,int s){
        //当cur的约数个数更多，或cur是约数个数最多的数中的更小值，则更新答案
        if(s>sum||s==sum&&curn)break;
            cur*=ps[idx];
            dfs(idx+1,i,cur,s*(i+1));
        }
    }
 
 
N - 接水问题二 
 
 解法参考：接水问题二
 关于排序：（第i个人的重要性是a[i]，需要b[i]的时间来接水） 
  
  1在前,2在后 sum = a[1] * b[1] + a[2] * ( b[1] + b[2] )
 2在前,1在后 sum = a[2] * b[2] + a[1] * ( b[1] + b[2] )
 所以只需要让 a[2] * b[1] < a[1] * b[2] 即可。 
  
 
	public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n=sc.nextInt();
        int p[][]=new int[n][2];
        for(int i=0;i() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]*o2[0]-o1[0]*o2[1];
            }
        });
        long time=0,sum=0;//每个人的等待时间 & 等待时间乘以自己的重要性的总和
        for(int i=0;i

【Java】贪心专题训练

Java相关栏目本月热门文章