某滴

题目描述

某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大

输入描述:

输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行，每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。

输出描述:

输出一个整数,表示最大的总预计消费金额

示例1

输入

3 5 2 4 2 1 3 3 5 3 7 5 9 1 10

输出

20

import java.util.*;
 public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int count=sc.nextInt();
        int guest=sc.nextInt();
        int[] gust_count=new int[guest];
        int[] gust_pr=new int[guest];
        int[] desk_Cap=new int[count];
        for (int i = 0; i < count; i++) {
            desk_Cap[i]=sc.nextInt();
        }
        Arrays.sort(desk_Cap);
        boolean[] isUsed = new boolean[count];//默认为false
        //使用优先队列来存储选择顾客组的顺序 先进先出
        Queue<Pval> Set = new PriorityQueue<Pval>();
        for (int i = 0; i < guest; i++) {
            gust_count[i]=sc.nextInt();
            gust_pr[i]=sc.nextInt();
            Set.add(new Pval(gust_count[i],gust_pr[i]));
        }
        sc.close();
    

        
        long sum=0;//int类型的数据相加可能超出范围
        
        while(!Set.isEmpty()) {
            Pval p=Set.poll();
            for (int i = 0; i < desk_Cap.length; i++) {
                if (desk_Cap[i]>=p.people&!isUsed[i]) {//isUsed数组用来记录该桌子是否被占用
                    sum=sum+p.value;
                    isUsed[i]=true;
                    break;
                }
            } 
        }
        System.out.println(sum);
    }
/将两个元素转化为可以比较的对象先将消费金额大的加入到队列当消费金额相同时先考虑人比较少的情况因为事先已经对桌子的容量客人数即第二行已经排序了 节省时间
    static class Pval implements Comparable<Pval>{
        int people;　　　　　　　　　　　　　　　　　　　
        int value;
        public Pval(int people, int value) {
            super();
            this.people = people;
            this.value = value;
        }
        @Override
        public int compareTo(Pval t) {
            if(this.value == t.value)
            {
                return this.people < t.people ? -1 : 1;
            }
            else
            {
                return this.value > t.value ? -1 : 1;
            }
             
        }
         
         
    }
 }

题目描述

输入一个正整数n,求n!(即阶乘)末尾有多少个0？ 比如: n = 10; n! = 3628800,所以答案为2

 import java.util.*;
public class Main {
 public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int data=sc.nextInt();
       int count=0;//分解质因数5注意25 125
        while (data/5!=0) {
            data=data/5;
            count=count+data;
        };
         System.out.println(count);
    }
    
 }

题目描述：连续最大和

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3 

输入描述:

输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。

输出描述: 

所有连续子数组中和最大的值。

 

输入例子1:

3 -1 2 1

 

输出例子1:

3

import java.util.*;
 public class Main {
     public static int getMaxSum(int[] a) {
         int sum[]=new int[a.length];
         sum[0]=a[0];
         int count=0;
         for (int i = 0; i < a.length; i++) {
             if(a[i]<0)
                count++;
         }
         if(count==a.length)
         {
             return a[0];//排除全是负值的情况
         }
         if(a[0]<0)
              sum[0]=0;//排除首个是-1的情况
         for (int i = 1; i < a.length; i++) {
             sum[i]=(sum[i-1]+a[i])>0?(sum[i-1]+a[i]):0;
        }
         Arrays.sort(sum);
         return sum[a.length-1];
     }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int count=sc.nextInt();
        int data[] =new int[count];
        for(int i=0;i<count;i++)
        {
            data[i]=sc.nextInt();
        }
        System.out.println(getMaxSum(data));
    }
 }

 [编程题] 进制转换

 给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数 

输入描述:

输入为一行，M(32位整数)、N(2 ≤ N ≤ 16)，以空格隔开。

输出描述:

为每个测试实例输出转换后的数，每个输出占一行。如果N大于9，则对应的数字规则参考16进制（比如，10用A表示，等等）

输入例子1:

7 2

输出例子1:

111

 import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int data=sc.nextInt();
        int jz=sc.nextInt();
        Stack<Object> stack=new Stack<>();
        int tempd=0;
        if (data<0) {//考虑负数的情况
            tempd=data;
            data=-data;
        }
        while(data!=0) {
            int temp=data%jz;
            if (temp>=10||temp<=15) {
                 String temp1=Integer.toHexString(temp).toUpperCase();
                 stack.push(temp1);
            }
            else {
                stack.push(temp);
            }
            data=data/jz;
        }
        String s="";
        while(!stack.isEmpty()) {
            s=s+stack.pop();
        }
        if (tempd<0) {
             System.out.println("-"+s);
        }else {
             System.out.println(s);
        }
    }
 }

题目描述

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

输入描述:

输入为两行:
第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
第二行为n个正整数A[i](32位整数)，以空格隔开。

输出描述:

输出所求的方案数

输入:

5 15

5 5 10 2 3

输出:

4

（1）首先构造初始值，即第一排和第一行

（2）对于从第一行第一列开始则若该行的data[i]即输入数据小于或等于j（构造出来的中间和）ar[i]要考虑ar[i-1][j]与arr[i-1][j-data[i]]之和，例如ar[3]10]=2+a[2][10-7]否则只考虑ar[i-1][j]即可

状态转移方程：

import java.util.*;
 public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int count=sc.nextInt();
        int sum=sc.nextInt();
        int[] data=new int[count+1];
        data[0]=0;
        for (int i = 1; i < count+1; i++) {
            data[i]=sc.nextInt();
        }
        long[][] ar=new long[count+1][sum+1];//int类型求和用long存储
        for (int i = 0; i < ar[0].length; i++) {
            ar[0][i]=0;
        }
        for (int i = 0; i < ar.length; i++) {
            ar[i][0]=1;
        }
        for (int i = 1; i < ar.length; i++) {
            for (int j = 1; j < ar[0].length; j++) {
                if (data[i]<=j) {
                    ar[i][j]=ar[i-1][j]+ar[i-1][j-data[i]];
                    
                }else {
                    ar[i][j]=ar[i-1][j];//确定初始值状态转移方程
                }
            }
        }
        System.out.println(ar[ar.length-1][ar[0].length-1]);
       
    }
 
}

题目描述:

给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0-10000的非负整数）的不同组合的个数。

输入描述:

输入为一个数字N，即需要拼凑的面额

输出描述:

输出也是一个数字，为组成N的组合个数。

示例1

输入

5

输出

2

package uestc;

import java.time.zone.ZoneRulesProvider;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Scanner;


public class Main {
      public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int money=scanner.nextInt();
        System.out.println(countWays(money));
      }
       public static int countWays(int money) {
           int[] data=new int[]{1,5,10,20,50,100};
           int[][] data_1=new int[6][money+1];
           for (int i = 0; i < data_1.length; i++) {
               data_1[i][0]=1;
            }
           for (int i = 0; i < data_1[0].length; i++) {
               data_1[0][i]=1;
            }
           for (int i = 1; i <data_1.length; i++) {
                for (int j = 1; j <data_1[i].length; j++) {
                    if (j>=data[i]) {
                        data_1[i][j]=data_1[i-1][j]+data_1[i][j-data[i]];
                    }
                    else {
                        data_1[i][j]=data_1[i-1][j];
                    }
                }
           }
//           for (int i = 0; i < data_1.length; i++) {
//            for (int j = 0; j < data_1[i].length; j++) {
//                System.out.print(data_1[i][j]+" ");
//            }
//            System.out.println();
//        }
           return data_1[5][money];
       }

}