Interview Questions
目录
Bytedance 实习 测试岗 2023.6
丢西瓜捡芝麻策略
解法一：直接从起点开始走，遇到比手上有的物品价格低的就换成买价格低的物品，直到终点，这样就能确保买到的价格最低。算法的时间复杂度为 $O(n)$。
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4#define MAX 100
5
6typedef struct Expense
7{
8 long int day;
9 long int cost;
10};
11
12int main()
13{
14 Expense arr[MAX];
15 long int min_cost = 1e9 + 7;
16 int k = 0;
17 long long int M, N, ans = 0;
18 memset(arr, 0, sizeof(arr));
19 scanf("%lld%lld", &M, &N);
20 for (int i = 0; i < N; i++)
21 {
22 scanf("%ld%ld", &arr[i].day, &arr[i].cost);
23 }
24 for (int i = 0; i < N; i++)
25 {
26 if (arr[i].cost < min_cost)
27 {
28 ans += arr[k].cost * (arr[i].day - arr[k].day);
29 k = i;
30 min_cost = arr[i].cost;
31 }
32 }
33 ans += arr[k].cost * (M - arr[k].day);
34 printf("%lld\n", ans);
35 return 0;
36}
解法二（贪心算法+计数排序）：先用计数排序从小到大排好各个补给站的物品价格，先选最小的物品价格作为起点，然后在该物品的补给站之前找到最小的物品价格，如此迭代，直到回到起点为止，这样取得的同样是最小的花费。算法时间复杂度为 $O(m*n)$
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#define MAX 10000
5
6typedef struct Travel
7{
8 long int day;
9 long int cost;
10}Expense;
11
12
13void print_arr(Expense* arr, int n) //打印排序结果
14{
15 int i;
16 printf("%d", arr[0].cost);
17 for (i = 1; i < n; i++)
18 {
19 printf(" %d", arr[i].cost);
20 }
21 printf("\n");
22}
23
24int main()
25{
26 long long int M, N;
27 int* count_arr = (int*)malloc(sizeof(int) * MAX);
28
29 memset(count_arr, 0, MAX);
30 scanf("%lld%lld", &M, &N);
31 Expense* sorted_arr = (Expense*)malloc(sizeof(Expense) * N);
32 Expense* arr = (Expense*)malloc(sizeof(Expense) * N);
33 for (int i = 0; i < N; i++)
34 {
35 arr[i].cost = arr[i].day = 0;
36 }
37 for (int i = 0; i < N; i++)
38 {
39 int j = scanf("%ld%ld", &arr[i].day, &arr[i].cost);
40 if (j == 2) //计数排序
41 {
42 count_arr[arr[i].cost]++;
43 }
44 while (char ch = getchar() != '\n');
45 }
46 print_arr(arr, N);
47 for (int k = 1; k < MAX; k++)//累加次数
48 {
49 count_arr[k] += count_arr[k - 1];
50 }
51 for (int j = N; j > 0; j--)
52 {
53 sorted_arr[--count_arr[arr[j - 1].cost]] = arr[j - 1];
54 }
55 print_arr(sorted_arr, N);
56 int k = 0;
57 long int remain_day = M, day = sorted_arr[k].day;
58 long long int total_cost = 0;
59 do
60 {
61 total_cost += (remain_day - sorted_arr[k].day) * sorted_arr[k].cost;
62 for (int i = 0; i < N; i++)
63 {
64 if (sorted_arr[i].day < sorted_arr[k].day)
65 {
66 day = sorted_arr[k].day;
67 remain_day = sorted_arr[k].day;
68 k = i;
69 break;
70 }
71 }
72 } while (sorted_arr[k].day != 0);
73 total_cost += day * sorted_arr[k].cost;
74 printf("%lld", total_cost);
75 free(arr);
76 free(count_arr);
77 free(sorted_arr);
78 return 0;
79}
