当前位置：首页 > news >正文

【算法训练营】最近点对，纸牌，青蛙（Python实现）

news 来源：原创 2024/5/10 5:08:27

最近点对

描述

给定n个二维平面上的点，求距离最近的一对点，输出他们的距离。

输入

第一行包含一个正整数n。

接下来n行，每行包含两个整数x,y，表示一个点的坐标。

输出

输出距离最近的一对点的距离，保留两位小数。

样例1输入

样例1输出

1.41

样例1解释

距离最近的点为7和8，距离为√(7−6)2+(5−6)2=√2≈1.41(7-6)2+(5-6)2=2≈1.41

样例2输入

点击下载

限制

对于70%的数据，2 ≤ n ≤ 2000，每个点坐标的绝对值不超过10^5；

对于100%的数据，2 ≤ n ≤ 3×10^5，每个点坐标的绝对值不超过10^9。

时间：10 sec

空间：512 MB

提示

[分治求最近点对。当然也可以用kdtree，虽然应该会超时。]

代码实现

import sys
from math import sqrtdef distance(point1, point2):return sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)def closest_pair(points, l, r):if l == r:return sys.float_info.maxif r - l == 1:return distance(points[l], points[r])mid = (l + r) // 2dl = closest_pair(points, l, mid)dr = closest_pair(points, mid + 1, r)min_d = min(dl, dr)mid_points = []for i in range(l, r + 1):if abs(points[i][0] - points[mid][0]) < min_d:mid_points.append(points[i])mid_points.sort(key=lambda point: point[1])for i in range(len(mid_points)):for j in range(i + 1, len(mid_points)):if mid_points[j][1] - mid_points[i][1] >= min_d:breakmin_d = min(min_d, distance(mid_points[i], mid_points[j]))return min_ddef main():n = int(input())points = [(0, 0)] * nfor i in range(n):points[i] = tuple(map(int, input().split()))points.sort(key=lambda point: point[0])ans = closest_pair(points, 0, n - 1)print(f"{ans:.2f}")if __name__ == "__main__":main()

纸牌

时间限制：1 sec

空间限制：512 MB

问题描述

小明有 2n 张纸牌，点数依次从1 到 2n。小明要和你玩一个游戏，这个游戏中，每个人都会分到 n 张卡牌。游戏一共分为 n 轮，每轮你们都要出一张牌，点数小者获胜。

游戏开始了，你拿到了你的牌。你现在想知道，你最多（也就是运气最好的情况下）能够获胜几轮？

输入格式

第一行 1 个正整数 n。

第 2 行到第 n+1 行每行一个正整数 a[i]，表示你的第 i 张牌的点数。

输出格式

一行一个整数表示你最多能够获胜的轮数。

样例输入

2
1
4

样例输出

数据范围

对于 31.25% 的数据，保证 1<=n<=100

对于 100% 的数据，保证 1<=n<=50,000

保证数据的合法性，即你即不会拿到重复的牌，又不会拿到超出点数范围的牌。

代码实现

#include <bits/stdc++.h>
using namespace std;int main() {int n;int x, cnt = 0;scanf("%d", &n);int N = 2 * n + 1;int a[N], b[N];memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));for (int i = 1; i <= n; ++i) {scanf("%d", &x);a[x] = x;}for (int j = 1; j <= 2 * n; j++)if (a[j] == 0) {b[j] = j;}int index1 = 1, index2 = 1;for (; index1 <= 2 * n, index2 <= 2 * n;) {for (; a[index1] == 0 && index1 < 2 * n; ++index1);for (; b[index2] == 0 && index2 < 2 * n; ++index2);if (a[index1] < b[index2]) {++cnt;++index1;++index2;} else {++index2;}}printf("%d", cnt);return 0;
}

青蛙

题目名称：小青蛙

时间限制：5 sec

空间限制：256 MB

问题描述

一个坐标轴上有 n个荷叶，编号从 11 到 n。每片荷叶有一个坐标。

有一只可爱的小青蛙，它任选一片荷叶作为起点，并选择一个方向（左或右）然后开始跳。第一次跳跃时，他没有任何限制。从第二次跳跃开始，受到魔法的影响，他每次跳跃的距离都必须不小于前一次跳跃的距离，且跳跃方向必须与上一次跳跃保持一致。

每一片荷叶上都有一个数值。每次小青蛙跳到一片荷叶上时，他就会获得该荷叶对应的数值。特别地，他初始选择的荷叶的数值也是能得到的。

小青蛙可以在任意时刻选择停止跳跃。

可爱的小青蛙希望能获得尽可能大的数值总和。你能帮帮她吗？

输入格式

输出格式

一行一个整数，表示小青蛙能够获得的最大的数值总和。

样例输入

样例输出

数据范围

提示

本题时间限制较大，可以考虑一些效率一般的算法哦！

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int MAX_LEAVES = 1005;
pair<int, int> leaves_coord[MAX_LEAVES];
int n;
int dp[MAX_LEAVES][MAX_LEAVES];int main() {cin >> n;// Read the coordinates of the leaves on the axisfor (int i = 1; i <= n; ++i) {int x, s;cin >> x >> s;leaves_coord[i] = make_pair(x, s);}int answer = 0;for (int round = 0; round < 2; ++round) {sort(leaves_coord + 1, leaves_coord + n + 1);for (int i = 1; i <= n; ++i) {dp[i][i] = leaves_coord[i].second;for (int j = 1; j < i; ++j) {dp[i][j] = 0;for (int k = j; k && 2 * leaves_coord[j].first <= leaves_coord[i].first + leaves_coord[k].first; --k)dp[i][j] = max(dp[i][j], dp[j][k]);answer = max(answer, (dp[i][j] += leaves_coord[i].second));}}// Reflect the leaves along the axis to continue using the sorting algorithmfor (int i = 1; i <= n; ++i)leaves_coord[i].first = -leaves_coord[i].first;}cout << answer << endl;return 0;
}