BGN29 小红的优惠券

贪心

描述

小红的购物车结算金额为 nn 元，她手中有 mm 张优惠券。第 jj 张优惠券的规则为“满 aja**j 元立减 bjb**j 元”，即若 n≧ajn≧a**j，则使用该券后需支付 n−bjn−b**j 元。

小红至多使用一张优惠券，请问最少需要支付多少元？

输入描述：

第一行输入两个整数 n,m(1≦n≦105; 1≦m≦100)n,m(1≦n≦105; 1≦m≦100)。
接下来 mm 行，第 jj 行输入两个整数 aj,bj(1≦bj≦aj≦105)a**j​,b**j​(1≦b**j​≦a**j​≦105)，描述第 jj 张优惠券。

输出描述：

输出一个整数，表示小红使用最优策略后需支付的最少金额。

示例1

输入：

1
2
3
4
100 3
300 50
200 30
50 5

输出：

1
95

说明：

1
仅第三张券可用，支付 100−5=95100−5=95 元。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int minprice = n;
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            if (a <= n) {
                minprice = Math.min(minprice, n - b);
            }
        }
        System.out.println(minprice);
    }
}

BGN30 讨厌鬼进货

贪心

描述

讨厌鬼需要采购 nn 种货物，每种货物可通过以下方式获取：
∙ ∙ 在供应商 AA 以 aia**i​ 元购得第 ii 种；
∙ ∙ 在供应商 BB 以 bib**i​ 元购得第 ii 种；
∙ ∙ 在网购平台一次性购买全部 nn 种，花费 xx 元（不能拆分）。

可以自由组合以上方式，只要最终每种货物都至少购买一件。求最小总花费。

输入描述：

第一行输入两个整数 n,x(1≦n≦105; 1≦x≦109)n,x(1≦n≦105; 1≦x≦109)。
第二行输入 nn 个整数 a1,a2,…,an(1≦ai≦104)a1​,a2​,…,a**n​(1≦a**i​≦104)。
第三行输入 nn 个整数 b1,b2,…,bn(1≦bi≦104)b1​,b2​,…,b**n​(1≦b**i​≦104)。

输出描述：

输出一个整数，表示完成采购的最少花费。

示例1

输入：

1
2
3
5 5
2 1 2 1 2
1 2 1 2 3

输出：

1
5

说明：

1
直接选择网购 55 元即可完成。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int x = in.nextInt();
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            a.add(in.nextInt());
        }
        for (int i = 0; i < n; i++) {
            b.add(in.nextInt());
        }
        
        for (int i = 0; i < n; i++) {
            int a1 = a.get(i);
            int b1 = b.get(i);
            if (a1 > b1) {
                ans += b1;
            }
            else {
                ans += a1;
            }
        }
        if (ans > x) {
            System.out.println(x);
        }
        else {
            System.out.println(ans);
        }

    }
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();

        int[] a = new int[n];
        int[] b = new int[n];

        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        for(int i = 0; i < n; i++){
            b[i] = sc.nextInt();
        }

        long sumMin = 0;
        for(int i = 0; i < n; i++){
            sumMin += Math.min(a[i], b[i]);
        }

        long ans = Math.min(sumMin, x);
        System.out.println(ans);
        sc.close();
    }
}

清楚姐姐买竹鼠

贪心

描述

清楚姐姐途经山村，遇到一家售卖竹鼠的商铺：
∙ ∙ 花费 a 元可购买 1 只竹鼠；

∙ ∙ 花费 b 元可购买 3 只竹鼠。

给定 a,b,x，求买到至少 x 只竹鼠所需的最小花费。

输入描述：

在一行上输入三个整数 a,b,x(1≦a,b,x≦10⁹)

输出描述：

输出一个整数，表示最少需花费的金额。

示例1

输入：

1
4 10 10

输出：

1
34

说明：

1
          花费 3×b=303×b=30 元买 99 只竹鼠，再花费 1×a=41×a=4 元买 11 只竹鼠，共花费 3434 元。我们可以证明，没有更优的购买方式。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            long a = in.nextLong();
            long b = in.nextLong();
            long x = in.nextLong();
            long na = 0;
            long nb = 0;
            long ans = 0;
            if (a > b/3 && a <b) {
                na = x % 3;
                nb = (x - na) / 3;
                ans = na * a + nb * b;
            }
            else if (a <= b/3) {
                ans = a * x;
            }
            else if (a >= b) {
                na = x % 3;
                nb = (x - na) / 3;
                ans = b * (na + nb);
            }
            System.out.println(ans);
        }
    }
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long x = sc.nextLong();
		
        // 买3的可能数
        long k1 = x / 3;  //整除
        long k2 = k1 + 1;  // 多买一套
        long k3 = 0;  // 一套不用买

        long res1 = calc(a,b,x,k1);
        long res2 = calc(a,b,x,k2);
        long res3 = calc(a,b,x,k3);
        
        // 每一组情况都计算，得出最优解
        long ans = Math.min( Math.min(res1,res2), res3 );
        System.out.println(ans);
        sc.close();
    }

    // k份3只套餐
    static long calc(long a, long b, long x, long k){
        long total = k *3;  // 买3套的总数
        if(total >= x){  // 如果大于等于x，说明3套多买或者正好
            return k * b;  // 返回3套数量*三套价格
        }else{
            long need = x - total;
            return k*b + need * a;  // 否则返回三套总价 + 单买总价
        }
    }
}