首页 > 代码库 > PAT 1048. Find Coins
PAT 1048. Find Coins
two sum题目,算是贪婪吧
#include <cstdio>#include <cstdlib>#include <vector>#include <algorithm>using namespace std;int main() { int N, M; scanf("%d%d", &N, &M); vector<int> coins(N); for (int i=0; i<N; i++) { scanf("%d", &coins[i]); } sort(coins.begin(), coins.end()); int p = 0, q = N - 1; while (p<q) { int sum = coins[p] + coins[q]; if (sum > M) { // bigger, so decrease it, move q to the smaller coins q--; } else if (sum < M) { // smaller, so increase it, move p to the bigger coins p++; } else { // we found the coins printf("%d %d\n", coins[p], coins[q]); break; } } if (p >= q) { printf("No Solution\n"); } return 0;}
PAT 1048. Find Coins
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。