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;
}