首页 > 试题广场 >

队列得分

[编程题]队列得分
  • 热度指数:2192 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

M和大M要通过选择元素组成队列进行得分pk。目前存在队列S1,S2,S3...Sn,每个元素包括2个正整数属性setvalue.从中选出任意K个元素S[i1],S[i2]...S[ik],保证顺序不变即i1 < i2 < i3< ... < ik,组成新的队列P1,P2,P3......Pk.我们通过一个机制评价队列的好坏:

Base=P1.value+P2.value+...Pk.value,

Bonus=10*t;t为新队列中Pi.set=P(i+1).seti个数.

最终得分Score=Base-Bonus;Score的最大值和取最大值时新队列元素个数的最小值.


输入描述:
第一行包含一个数N(0 < N <= 500)

接下来N行每一行两个数表示S1,S2,...,Sn的set和value值 (0 < set,value <= 20)


输出描述:
Score的最大值和新队列元素个数的最小值
示例1

输入

5
1 10
1 5
2 4
3 9
4 8

输出

31 4

说明

选S1,S3,S4,S5
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(br.readLine());
        String[] arr0 = br.readLine().split(" ");
        int t1 = Integer.parseInt(arr0[0]);
        int t2 = Integer.parseInt(arr0[1]);
        int sum = t2;
        int eqnum = 0;
        String line = "";
        while ((line = br.readLine()) != null) {
            String[] arr = line.split(" ");
            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);
            if (a == t1) {
                if (t2 <= 10 || b <= 10) {
                    b = Math.max(b, t2);
                    length--;
                } else {
                    t2 = 0;
                    eqnum++;
                }
            } else {
                t2 = 0;
            }
            sum += b - t2;
            t1 = a;
            t2 = b;
        }
        System.out.println((sum - eqnum * 10) + " " + length);
    }
}

编辑于 2024-02-22 09:52:39 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sum = 0;int count = n;
        int tempSet = 0;
        int tempVal = 0;
        for(int i = 0; i < n; i++){
            boolean flag = false;
            int set = sc.nextInt();
            int value = sc.nextInt();
            if(set == tempSet){
//                 两个都比10大,都加入
                if(10 < tempVal && 10 < value){
                    sum -= 10;
                }else{
                    //一个比10大,或者都没有10大,加一个
                    if(tempVal < value){
                        sum -= tempVal;
                    }else{
                        sum -= value;
//                         是为了让tempVal为之前的数
                        flag = true;
                    }
                    count--;
                }
            }
            tempSet = set;
            if(!flag) 
                tempVal = value;
            sum += value;
        }
        System.out.print(sum+" "+count);
    }
}
发表于 2021-12-04 15:08:17 回复(0)