1048 Find Coins (25 分)

mac2025-01-18  59

1048 Find Coins (25 分)

题目入口:https://pintia.cn/problem-sets/994805342720868352/problems/994805432256675840

目录

1048 Find Coins (25 分)思想AC代码TLE代码问题测试点四TLE代码

思想

分析题目发现总金额数量级为103 所以可以开一个相应大小的数组 预处理硬币金额映射到数组下标 同时得到最小金额硬币Min和最大金额硬币Max 从小遍历中间的金额符合题目思想 具体细节不加解释 无非是条件决策 到这里讲解结束

AC代码

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1e5+10; const int MAXN2 = 1e3+10; #define mm(a) memset(a,0,sizeof(a)) #define inf 0x3f3f3f3f int a[MAXN]; int b[MAXN2]; int main(){ int n, m; scanf("%d%d", &n, &m); mm(b); int Min = inf, Max = -inf; for (int i = 0; i < n; i++){ scanf("%d", &a[i]); if (a[i] < Min) Min = a[i]; if (a[i] > Max) Max = a[i]; b[a[i]]++; } for (int i = Min; i <= Max; i++){ if (b[i] && b[m-i]){ if (m == 2*i){ if (b[i] > 1){ printf("%d %d\n", i, i); return 0; } } else{ printf("%d %d\n", i, m-i); return 0; } } } printf("No Solution\n"); return 0; }

TLE代码问题

剪枝没剪好?我没再花时间去改 想到上面的代码思路就转过去写了 有时间再来这里改一改吧

测试点四TLE代码

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1e5+10; int a[MAXN]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a+n); for (int i = 0; i < n; i++){ for (int j = n-1; j > i; j--){ if (a[i]+a[j] < m) break; if (a[i]+a[j] == m){ printf("%d %d\n", a[i], a[j]); return 0; } } } printf("No Solution\n"); return 0; }
最新回复(0)