#M9016. 入门算法

入门算法

当前没有测试数据。

  1. 填空题

完善程序： (过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n(2≤n<100)和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。 例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为2+1+4=7。

#include <iostream>
using namespace std;

const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;

int n, hour[SIZE];
bool pos[SIZE];

int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int go(bool stage)
{
    int i, j, num, tmp, ans;
    if (stage == RIGHT_TO_LEFT) {
        num = 0;
        ans = 0;
        for (i = 1; i <= n; i++)
            if (pos[i] == RIGHT) {
                num++;
                if (hour[i] > ans)
                    ans = hour[i];
            }
        if ([    ①    ])
            return ans;
        ans = INFINITY;
        for (i = 1; i <= n - 1; i++)
            if (pos[i] == RIGHT)
                for (j = i + 1; j <= n; j++)
                    if (pos[j] == RIGHT) {
                        pos[i] = LEFT;
                        pos[j] = LEFT;
                        tmp = max(hour[i], hour[j]) +[ ② ];
                        if (tmp < ans)
                           ans = tmp;
                        pos[i] = RIGHT;
                        pos[j] = RIGHT;
                    }
        return ans;
    }
    if (stage == LEFT_TO_RIGHT) {
        ans = INFINITY;
        for (i = 1; i <= n; i++)
            if ([    ③    ]) {
                pos[i] = RIGHT;
                tmp =[    ④    ];
                if (tmp < ans)
                    ans = tmp;
            [        ⑤    ];
            }
        return ans;
    }
    return 0;
}

int main()
{
    int i;
        
    cin>>n;
    for (i = 1; i <=n; i++) {
        cin>>hour[i];
        pos[i] = RIGHT;
    }
    cout<<go(RIGHT_TO_LEFT)<<endl;
    return 0;
}

第一空：{{ input(1) }}
第二空：{{ input(2) }}
第三空：{{ input(3) }}
第四空：{{ input(4) }}
第五空：{{ input(5) }}

  1. 填空题

阅读程序写结果

image

输入：
11
4 5 6 6 4 3 3 2 3 2 1
输出：_____________
{{ input(6) }}

  1. 填空题

阅读程序写结果

image

输入：7 4
输出：________
{{ input(7) }}

  1. 填空题

完善程序 （坐标统计）输入𝑛n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。

image

第一空：{{ input(8) }}
第二空：{{ input(9) }}
第三空：{{ input(10) }}
第四空：{{ input(11) }}
第五空：{{ input(12) }}

  1. 填空题

阅读程序写结果：

image

输入：
6
2 5 3 11 12 4
输出：___________
{{ input(13) }}

  1. 填空题

如图所示，图中每条边上的数字表示该边的长度，则从𝐴A到𝐸E的最短距离是？

image

{{ input(14) }}

  1. 填空题

阅读程序写结果:

image

输入：15
输出：_____
{{ input(15) }}

  1. 填空题

阅读程序写结果:

image

输入：10 7 1 4 3 2 5 9 8 0 6
输出：__________________
{{ input(16) }}

  1. （Josephus 问题）有 n 个人围成一个圈，依次标号 0 至 n−1。从 0 号开始，依次 0, 1, 0, 1, ... 交替报数，报到 1 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。 试补全模拟程序。
1 	#include <stdio.h>
2 
3 	const int MAXN = 1000000;
4 	int F[MAXN];
5 
6 	int main(){
7 		int n;
8 		scanf("%d", &n);
9 		int i = 0, p = 0, c = 0;
10		while( ①){
11			if (F[i] == 0){
12				if ( ② ){
13					F[i] = 1;
14					③; 
15				}
16				④; 
17			}
18			⑤; 
19		} 
20		int ans = -1;
21		for (int i = 0; i < n; i++)
22			if (F[i] == 0)
23				ans = i;
24		printf("%d\n", ans);
25		return 0;
26	}

①处应填？ {{ select(17) }}

  • i < n
  • c < n
  • i < n - 1
  • c < n - 1 ②处应填？ {{ select(18) }}
  • i % 2 == 0
  • i % 2 == 1
  • p
  • !p ③处应填？ {{ select(19) }}
  • i++
  • i = (i+1) % n
  • c++
  • p ^= 1 ④处应填？ {{ select(20) }}
  • i++
  • i = (i+1) % n
  • c++
  • p ^= 1 ⑤处应填？ {{ select(21) }}
  • i++
  • i = (i+1) % n
  • c++
  • p ^= 1

  1. （矩形计数）平面上有𝑛n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。 试补全枚举算法。
1 	#include <stdio.h>
2 
3 	struct point {
4 		int x, y, id;
5 	};
6 
7 	int equals(struct point a, struct point b){
8 		return a.x == b.x && a.y == b.y;
9 	}
10
11	int cmp(struct point a, struct point b){
12		return  ①; 
13	}
14
15	void sort(struct point A[], int n){
16		for (int i = 0; i < n; i++)
17			for (int j = 1; j < n; j++)
18				if (cmp(A[j], A[j - 1])){
19					struct point t = A[j];
20					A[j] = A[j - 1];
21					A[j - 1] = t;
22				}
23	}
24
25	int unique(struct point A[], int n){
26		int t = 0;
27		for (int i = 0; i < n; i++)
28			if (②)
29				A[t++] = A[i];
30		return t;
31	}
32
33	int binary_search(struct point A[], int n, int x, int y){
34		struct point p;
35		p.x = x;
36		p.y = y;
37		p.id = n;
38		int a = 0, b = n - 1;
39		while(a < b){
40			int mid = ③;
41			if (④)
42				a = mid + 1;
43			else 
44				b = mid; 
45		}
46			return equals(A[a], p);
47	}
48
49	#define MAXN 1000
50	struct point A[MAXN];
51
52	int main(){
53		int n;
54		scanf("%d", &n);
55		for (int i = 0; i < n; i++){
56			scanf("%d %d", &A[i].x, &A[i].y);
57			A[i].id = i;
58		}
59		sort(A, n);
60		n = unique(A, n);
61		int ans = 0;
62		for (int i = 0; i < n; i++)
63			for (int j = 0; j < n; j++)
64			if ( ⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)){
65							ans++;
66			}
67		printf("%d\n", ans); 
68		return 0;
69	}

①处应填？ {{ select(22) }}

  • a.x != b.x ? a.x < b.x : a.id < b.id
  • a.x != b.x ? a.x < b.x : a.y < b.y
  • equals(a,b) ? a.id < b.id : a.x < b.x
  • equals(a,b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y) ②处应填？ {{ select(23) }}
  • i == 0 || cmp(A[i], A[i - 1])
  • t == 0 || equals(A[i], A[t - 1])
  • i == 0 || !cmp(A[i], A[i - 1])
  • t == 0 || !equals(A[i], A[t - 1]) ③处应填？ {{ select(24) }}
  • b - (b - a) / 2 + 1
  • (a + b + 1) >> 1
  • (a + b) >> 1
  • a + (b - a + 1) / 2 ④处应填？ {{ select(25) }}
  • !cmp(A[mid], p)
  • cmp(A[mid], p)
  • cmp(p, A[mid])
  • !cmp(p, A[mid]) ⑤处应填？ {{ select(26) }}
  • A[i].x == A[j].x
  • A[i].id < A[j].id
  • A[i].x == A[j].x && A[i].id < A[j].id
  • A[i].x < A[j].x && A[i].y < A[j].y
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  1. 渝ICP备2024028990号
  2. © 2021-2024 Hydro.ac
  4. Worker 0 in 81ms
  5. Hydro v4.16.0 Professional