10
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8

1.41

代码实现 

import sys
from math import sqrt


def 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.max
    if r - l == 1:
        return distance(points[l], points[r])

    mid = (l + r) // 2
    dl = 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:
                break
            min_d = min(min_d, distance(mid_points[i], mid_points[j]))

    return min_d


def main():
    n = int(input())
    points = [(0, 0)] * n
    for 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

样例输出

1

数据范围

对于 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。每片荷叶有一个坐标。

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

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

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

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

输入格式

输出格式

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

样例输入

6
5 6
1 1
10 5
7 6
4 8
8 10

样例输出

25

数据范围

提示

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

代码实现 

#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 axis
    for (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 algorithm
        for (int i = 1; i <= n; ++i)
            leaves_coord[i].first = -leaves_coord[i].first;
    }
    
    cout << answer << endl;
    return 0;
}