2025寒假算法练习——Week 5

2025-02-15 · 11 分钟阅读 · 算法贪心策略 dfs ·

复制链接:

文章目录

前几天出去旅游所以没咋做题。

习题均来自 NEFU OJ

Problem 75 | 老鼠的旅行

Description

一只老鼠有M磅猫食，然后在N个房间里面用猫食换JavaBean，房间i中能用F[i]磅的猫食来换J[i]磅的JavaBean，而且老鼠可以在一个房间里根据一定比例a%来换取JavaBean.
现在他是这任务分配给你：告诉他，他的JavaBeans的获取能最多。

Input

The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1′s. All integers are not greater than 1000.
M是开始时老鼠有的猫食！

Output

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

Sample Input

Sample Output

113.333
231.500

Hint

贪心

Source

ZJCPC2004

简单的贪心策略，从兑换比率最高的房间开始依次兑换。

 1import java.util.Scanner;
 2import java.util.List;
 3import java.util.ArrayList;
 4import java.util.stream.Collectors;
 5
 6public class Main {
 7    public static void main(String[] args) {
 8        int M, N;
 9        double J, F, ratio;
10        List<double[]> rooms = new ArrayList<>();
11        double j, f, r, ans = 0.0;
12        try (Scanner sc = new Scanner(System.in)) {
13            while (true) {
14                rooms.clear();
15                ans = 0.0;
16
17                M = sc.nextInt();
18                N = sc.nextInt();
19                if (M == -1) {
20                    return;
21                }
22
23                for (int i = 0; i < N; i++) {
24                    J = sc.nextDouble();
25                    F = sc.nextDouble();
26                    ratio = J / F;
27                    rooms.add(new double[] { J, F, ratio });
28                }
29
30                List<double[]> sorted = rooms.stream()
31                        .sorted((a, b) -> Double.compare(b[2], a[2]))
32                        .collect(Collectors.toList());
33
34                for (double[] room : sorted) {
35                    j = room[0];
36                    f = room[1];
37                    r = room[2];
38                    if (M >= f) {
39                        ans += j;
40                        M -= f;
41                    } else {
42                        ans += r * M;
43                        break;
44                    }
45                }
46
47                System.out.println(String.format("%.3f", ans));
48            }
49        }
50    }
51}

Problem 88 | Moving Tables

Description

The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.

The floor has 200 rooms each on the north side and south side along the corridor. Recently the Company made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because the corridor is narrow and all the tables are big, only one table can pass through the corridor. Some plan is needed to make the moving efficient. The manager figured out the following plan: Moving a table from a room to another room can be done within 10 minutes. When moving a table from room i to room j, the part of the corridor between the front of room i and the front of room j is used. So, during each 10 minutes, several moving between two rooms not sharing the same part of the corridor will be done simultaneously. To make it clear the manager illustrated the possible cases and impossible cases of simultaneous moving.

For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager’s problem.

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case begins with a line containing an integer N , 1<=N<=200 , that represents the number of tables to move. Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t (each room number appears at most once in the N lines). From the N+3-rd line, the remaining test cases are listed in the same manner as above.

Output

The output should contain the minimum time in minutes to complete the moving, one per line.

Sample Input

Sample Output

110
220
330

Source
hdu

这道题其实是找不重复区间。第一步将上下的区间统一，这样处理后 1 -> 3、2 -> 4、1 -> 4、2 -> 4 就是同一段区间。然后遍历全部区间，只要没有重复部分就可以在同一回合移动。

需要注意存储区间时需要让左端点小于等于右端点，且存储的区间要按照左右端点依次排序。

 1import java.util.Scanner;
 2import java.util.List;
 3import java.util.ArrayList;
 4import java.util.stream.Collectors;
 5
 6public class Main {
 7    public static void main(String[] args) {
 8        Scanner sc = new Scanner(System.in);
 9        int T = sc.nextInt();
10        List<int[]> moves = new ArrayList<>();
11
12        int N, s, t, step;
13        while (T-- > 0) {
14            moves.clear();
15            N = sc.nextInt();
16            step = N;
17            boolean[] moved = new boolean[N];
18
19            for (int j = 0; j < N; j++) {
20                s = sc.nextInt();
21                t = sc.nextInt();
22                int[] move = new int[] { Math.min(s, t), Math.max(s, t) };
23                for (int i = 0; i <= 1; i++) {
24                    if (move[i] % 2 == 0) {
25                        move[i] /= 2;
26                    } else {
27                        move[i] = (move[i] + 1) / 2;
28                    }
29                }
30                moves.add(move);
31            }
32
33            List<int[]> sorted = moves.stream()
34                    .sorted((a, b) -> {
35                        if (a[0] != b[0]) {
36                            return Integer.compare(a[0], b[0]);
37                        } else {
38                            return Integer.compare(a[1], b[1]);
39                        }
40                    }).collect(Collectors.toList());
41
42            int time = 0;
43            while (step > 0) {
44                int[] current = new int[2];
45                int i;
46                for (i = 0; i < N; i++) {
47                    if (!moved[i]) {
48                        current = sorted.get(i);
49                        moved[i] = true;
50                        step--;
51                        break;
52                    }
53                }
54
55                for (; i < N; i++) {
56                    if (!moved[i] && sorted.get(i)[0] > current[1]) {
57                        current = sorted.get(i);
58                        moved[i] = true;
59                        step--;
60                    }
61                }
62                time += 10;
63            }
64
65            System.out.println(time);
66        }
67        sc.close();
68    }
69}

Problem 89 | Wooden Sticks

Description

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l <= l' and w <= w'. Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1 <= n <= 5000 , that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l1 , w1 , l2 , w2 ,..., ln , wn , each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

Output

The output should contain the minimum setup time in minutes, one per line.

Sample Input

13
25
34 9 5 2 2 1 3 5 1 4
43
52 2 1 1 2 2
63
71 3 2 2 3 1

Sample Output

12
21
33

Source

taejon2001

将所有木棍依次按照 l 和 w 排序，从小到大处理木棍，代码和上一题类似。

 1import java.util.Scanner;
 2import java.util.List;
 3import java.util.ArrayList;
 4
 5public class Main {
 6    public static void main(String[] args) {
 7        Scanner sc = new Scanner(System.in);
 8
 9        int l, w, n;
10        List<int[]> sticks = new ArrayList<>();
11
12        int T = sc.nextInt();
13        while (T-- > 0) {
14            sticks.clear();
15            n = sc.nextInt();
16            boolean[] solved = new boolean[n];
17            int step = n;
18            for (int i = 0; i < n; i++) {
19                l = sc.nextInt();
20                w = sc.nextInt();
21                sticks.add(new int[] { l, w });
22            }
23
24            sticks.sort((a, b) -> {
25                if (a[0] != b[0]) {
26                    return Integer.compare(a[0], b[0]);
27                } else {
28                    return Integer.compare(a[1], b[1]);
29                }
30            });
31
32            int time = 0;
33            int[] current = new int[2];
34            while (step > 0) {
35                int i;
36                for (i = 0; i < n; i++) {
37                    if (!solved[i]) {
38                        current = sticks.get(i);
39                        step--;
40                        solved[i] = true;
41                        break;
42                    }
43                }
44
45                for (; i < n; i++) {
46                    if (!solved[i] && sticks.get(i)[1] >= current[1]) {
47                        current = sticks.get(i);
48                        solved[i] = true;
49                        step--;
50                    }
51                }
52
53                time++;
54            }
55            System.out.println(time);
56        }
57        sc.close();
58    }
59}

Problem 90 | 今年暑假不AC

Description

“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

Input

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

Output

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

Sample Input

Sample Output

Hint

贪心

Source

hdu lcy

这道题还是要找不重复区间。依次按照节目的结束时间和开始时间排序，随后按顺序找到可以播放的节目。

 1import java.util.Scanner;
 2import java.util.List;
 3import java.util.ArrayList;
 4
 5public class Main {
 6    public static void main(String[] args) {
 7        Scanner sc = new Scanner(System.in);
 8        int n, s, e;
 9        List<int[]> programs = new ArrayList<>();
10        while (true) {
11            n = sc.nextInt();
12            programs.clear();
13            if (n == 0) {
14                sc.close();
15                return;
16            }
17            for (int i = 0; i < n; i++) {
18                s = sc.nextInt();
19                e = sc.nextInt();
20                programs.add(new int[] { s, e });
21            }
22
23            programs.sort((a, b) -> {
24                if (a[1] != b[1]) {
25                    return Integer.compare(a[1], b[1]);
26                } else {
27                    return Integer.compare(a[0], b[0]);
28                }
29            });
30
31            int[] current = new int[] { 0, 0 };
32            int count = 0;
33            for (int[] program : programs) {
34                if (program[0] >= current[1]) {
35                    count++;
36                    current = program;
37                }
38            }
39            System.out.println(count);
40        }
41    }
42}

最开始提交忘记在每一组样例输入时 programs.clear() 清空上一组样例了，导致一直错。

感觉用 C++ 的结构体会更方便：

 1#include <algorithm>
 2#include <iostream>
 3
 4using namespace std;
 5
 6struct program {
 7	int s, e;
 8};
 9
10program programs[100];
11
12bool cmp(program a, program b) {
13	if (a.e != b.e) {
14		return a.e < b.e;
15	}
16	else {
17		return a.s < b.s;
18	}
19}
20
21int main() {
22	int n;
23	while (cin >> n)
24	{
25		if (n == 0) {
26			return 0;
27		}
28
29		for (int i = 0; i < n; i++) {
30			cin >> programs[i].s >> programs[i].e;
31		}
32
33		sort(programs, programs + n, cmp);
34
35		program p;
36		p.s = 0;
37		p.e = 0;
38		int count = 0;
39		for (int i = 0; i < n; i++) {
40			if (programs[i].s >= p.e) {
41				p = programs[i];
42				count++;
43			}
44		}
45		cout << count << endl;
46
47	}
48}

深搜解法：

 1import java.util.Scanner;
 2import java.util.Arrays;
 3
 4public class Main {
 5    public static void main(String[] args) {
 6        Scanner sc = new Scanner(System.in);
 7        while (true) {
 8            int n = sc.nextInt();
 9            if (n == 0) {
10                sc.close();
11                return;
12            }
13
14            Program[] programs = new Program[n];
15            for (int i = 0; i < n; i++) {
16                programs[i] = new Program();
17                programs[i].s = sc.nextInt();
18                programs[i].e = sc.nextInt();
19            }
20
21            Arrays.sort(programs, (a, b) -> {
22                if (a.e != b.e) {
23                    return Integer.compare(a.e, b.e);
24                } else {
25                    return Integer.compare(a.s, b.s);
26                }
27            });
28
29            int count = dfs(programs, -1, 0, n, 0);
30            System.out.println(count);
31        }
32    }
33
34    public static int dfs(Program[] programs, int t, int count, int n, int k) {
35        int max_count = count;
36        for (int i = k; i < n; i++) {
37            if (programs[i].s >= t) {
38                max_count = Math.max(max_count, dfs(programs, programs[i].e, count + 1, n, i + 1));
39            }
40        }
41
42        return max_count;
43    }
44}
45
46class Program {
47    public int s = 0, e = 0;
48}