题意分析

题目要求通过组合不同类型的电子硬币，使得其传统价值总和$X$和信息技术价值总和$Y$满足$\sqrt{X^2 + Y^2} = S$。需要找出达到该电子模数所需的最少硬币数量。

解题思路

1. 状态表示：将问题转化为在二维平面上从原点$(0,0)$出发，通过硬币的向量移动，寻找达到半径为$S$的圆上的点的最短路径。
2. BFS搜索：使用广度优先搜索遍历所有可能的$(X,Y)$组合，记录到达每个点的最小硬币数。
3. 剪枝优化：只考虑满足$X^2 + Y^2 \leq S^2$的点，避免无效搜索。

实现步骤

1. 输入处理：读取硬币类型和电子模数$S$。
2. BFS初始化：从原点$(0,0)$开始，步数初始化为0。
3. 状态扩展：对每个状态，尝试使用所有硬币类型进行扩展。
4. 终止条件：当找到满足$X^2 + Y^2 = S^2$的点时返回当前步数。
5. 结果输出：根据搜索结果输出最少硬币数或"not possible"。

C++实现

#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;

int n, s, m;
int vis[2100][2100]; // 访问标记数组

struct Coin {
    int x, y;
} coins[2100];

struct Node {
    int x, y, step;
};

int bfs() {
    queue<Node> Q;
    Node start = {0, 0, 0};
    vis[0][0] = 1;
    Q.push(start);

    while (!Q.empty()) {
        Node curr = Q.front();
        Q.pop();

        if (curr.x * curr.x + curr.y * curr.y == s * s) {
            return curr.step;
        }

        for (int i = 0; i < m; i++) {
            int nx = curr.x + coins[i].x;
            int ny = curr.y + coins[i].y;
            
            if (nx * nx + ny * ny <= s * s && !vis[nx][ny]) {
                vis[nx][ny] = 1;
                Q.push({nx, ny, curr.step + 1});
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d", &n);
    while (n--) {
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &m, &s);
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &coins[i].x, &coins[i].y);
        }
        int res = bfs();
        if (res >= 0) printf("%d\n", res);
        else printf("not possible\n");
    }
    return 0;
}

代码说明

1. 数据结构：
   • Coin结构体存储硬币的传统价值和信息技术价值。
   • Node结构体记录当前状态坐标和步数。
2. BFS实现：
   • 使用队列进行广度优先搜索。
   • vis数组标记已访问的点，避免重复计算。
3. 优化处理：
   • 只扩展满足$X^2 + Y^2 \leq S^2$的点。
   • 及时终止搜索，找到解立即返回。
4. 复杂度分析：
   • 时间复杂度：最坏$O(S^2)$，实际运行效率较高。
   • 空间复杂度：$O(S^2)$，由vis数组大小决定。