Apple Delivery 题解

题目分析

Ingrid 需要将苹果分发给无限平面上的邻居，每个整数坐标点有一栋房子。她的分发策略是：

• 选择一组半径 $r_1, r_2, \cdots, r_N$
• 对于每个半径 $r_i$，给所有满足 $x^2 + y^2 \leq r_i^2$ 的房子分发一个苹果
• 苹果装在每箱8个的盒子里，因此需要确保分发的苹果总数是8的倍数
• 可以通过删除一些半径来实现，但要最小化未分发的苹果数量

解题思路

核心问题转化

设总苹果数为 $S$，需要删除一些半径使得剩下的苹果数 $S' \equiv 0 \pmod{8}$。
等价于找到删除的苹果数 $T$ 满足 $T \equiv S \pmod{8}$，且 $T$ 最小。

关键步骤

1. 计算每个半径对应的苹果数：半径为 $r$ 的圆内整点个数
2. 模8分组：将苹果数按模8的余数分组
3. 动态规划求解：找到和模8等于 $S \bmod 8$ 的最小子集和

算法优化

• 每个余数组只需保留最小的几个值（最多8个）
• 使用动态规划在模8的有限状态空间中搜索
• 考虑单个值和多个相同值的情况

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 8
#define INF (1LL << 60)

typedef long long ll;

// 计算半径为r的圆内整点个数
ll count_points(int r) {
    if (r == 0) return 1;
    
    ll total = 0;
    ll r2 = (ll)r * r;
    
    // 使用更高效的方法计算圆内整点
    // 对于x从0到r，计算y的最大值
    int x = 0;
    int y = r;
    ll points = 0;
    
    while (x <= r) {
        while (y >= 0 && (ll)x * x + (ll)y * y > r2) {
            y--;
        }
        if (y < 0) break;
        // 对于当前x，y从-y到y都是整点，共2y+1个点
        // 但x=0时已经包含在初始情况中
        points += 2 * y + 1;
        x++;
    }
    
    return points;
}

int main() {
    int N;
    scanf("%d", &N);
    
    int *radii = (int*)malloc(N * sizeof(int));
    ll total_apples = 0;
    
    // 读取半径并计算总苹果数
    for (int i = 0; i < N; i++) {
        scanf("%d", &radii[i]);
        ll points = count_points(radii[i]);
        total_apples += points;
    }
    
    int target = total_apples % MOD;
    if (target == 0) {
        printf("0\n");
        free(radii);
        return 0;
    }
    
    // 计算每个半径对应的苹果数，并按模8分组
    ll mod_groups[MOD][8]; // 每个余数组存储最多8个最小的苹果数
    int mod_count[MOD] = {0};
    
    for (int i = 0; i < N; i++) {
        ll points = count_points(radii[i]);
        int rem = points % MOD;
        
        // 如果数组未满，直接添加
        if (mod_count[rem] < 8) {
            mod_groups[rem][mod_count[rem]++] = points;
        } else {
            // 找到最大值并替换
            int max_idx = 0;
            for (int j = 1; j < 8; j++) {
                if (mod_groups[rem][j] > mod_groups[rem][max_idx]) {
                    max_idx = j;
                }
            }
            if (points < mod_groups[rem][max_idx]) {
                mod_groups[rem][max_idx] = points;
            }
        }
    }
    
    // 对每个组进行排序
    for (int i = 0; i < MOD; i++) {
        if (mod_count[i] > 0) {
            // 简单排序
            for (int j = 0; j < mod_count[i] - 1; j++) {
                for (int k = j + 1; k < mod_count[i]; k++) {
                    if (mod_groups[i][j] > mod_groups[i][k]) {
                        ll temp = mod_groups[i][j];
                        mod_groups[i][j] = mod_groups[i][k];
                        mod_groups[i][k] = temp;
                    }
                }
            }
        }
    }
    
    // 动态规划：dp[i]表示达到余数i所需的最小苹果数
    ll dp[MOD];
    for (int i = 0; i < MOD; i++) {
        dp[i] = INF;
    }
    dp[0] = 0;
    
    // 对于每个余数组
    for (int rem = 0; rem < MOD; rem++) {
        if (mod_count[rem] == 0) continue;
        
        // 创建临时dp数组
        ll new_dp[MOD];
        for (int i = 0; i < MOD; i++) {
            new_dp[i] = dp[i];
        }
        
        // 尝试使用该组中的每个值
        for (int i = 0; i < mod_count[rem]; i++) {
            ll val = mod_groups[rem][i];
            
            // 单个值
            for (int j = 0; j < MOD; j++) {
                if (dp[j] != INF) {
                    int new_rem = (j + val) % MOD;
                    if (dp[j] + val < new_dp[new_rem]) {
                        new_dp[new_rem] = dp[j] + val;
                    }
                }
            }
            
            // 多个相同值（最多7个）
            for (int count = 2; count <= 7; count++) {
                ll sum_val = val * count;
                int sum_rem = (rem * count) % MOD;
                
                for (int j = 0; j < MOD; j++) {
                    if (dp[j] != INF) {
                        int new_rem = (j + sum_rem) % MOD;
                        if (dp[j] + sum_val < new_dp[new_rem]) {
                            new_dp[new_rem] = dp[j] + sum_val;
                        }
                    }
                }
            }
        }
        
        // 更新dp
        for (int i = 0; i < MOD; i++) {
            dp[i] = new_dp[i];
        }
    }
    
    printf("%lld\n", dp[target]);
    
    free(radii);
    return 0;
}

关键算法说明

1. 圆内整点计算

使用高效算法计算半径为 $r$ 的圆内整数坐标点个数：

• 对于每个 $x$ 从 $0$ 到 $r$，找到最大的 $y$ 使得 $x^2 + y^2 \leq r^2$
• 对于每个 $x$，有 $2y + 1$ 个整点（考虑对称性）

2. 模8分组优化

• 将苹果数按模8的余数分组
• 每组只保留最小的8个值，因为模8运算中，使用更多或更大的值不会得到更优解

3. 动态规划求解

• 状态：dp[i] 表示得到余数 i 所需的最小苹果数
• 转移：对于每个余数组，尝试使用单个值和多个相同值更新状态
• 目标：找到 dp[target]，其中 target = S % 8

复杂度分析

• 整点计算：$O(\max(r_i))$
• 分组排序：$O(N + 8^2)$
• 动态规划：$O(8^3)$
• 总复杂度：$O(N + \max(r_i))$，满足题目要求

样例验证

样例输入

6
1 0 2 1 0 0

计算过程

• 半径0：1个点
• 半径1：5个点
• 半径2：13个点
• 总苹果数：$1 + 5 + 13 + 5 + 1 + 1 = 26$
• $26 \bmod 8 = 2$
• 删除2个半径0（共2个苹果），剩下24个苹果（8的倍数）

输出

2

该解法充分利用了模运算的性质和动态规划的高效性，能够在给定约束下快速求解。