专栏首页vblogPAT 1048 Find Coins (25分) 硬币面值做数组下标即排序

PAT 1048 Find Coins (25分) 硬币面值做数组下标即排序

题目

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she could only use exactly two coins to pay the exact amount. Since she has as many as 105​​ coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.

Input Specification: Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (≤105​​ , the total number of coins) and M (≤10​3​​ , the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.

Output Specification: For each test case, print in one line the two face values V1 and V2 (separated by a space) such that V​1​​ +V2​​ = M and V​1​​ ≤V​2​​ . If such a solution is not unique, output the one with the smallest V​1​​ . If there is no solution, output No Solution instead.

Sample Input 1:

8 15
1 2 8 7 2 4 11 15

Sample Output 1:

4 11

Sample Input 2:

7 14
1 8 7 2 4 11 15

Sample Output 2:

No Solution

解析

题目:

给出n个正整数序列和一个目标值m。要求找出一对数字满足a+b=m,若这样的ab不唯一,则选择所有满足和为m的整数对中a值最小的那个。若不存在,输出"No Solution"

思路:

  • 因为最终结果涉及到一个大小顺序的问题,所以我们直接让每一个数字作为数组元素的下标,统计其出现的次数,这样的化借助于下标就自动实现了排序,然后我们按顺序遍历数组元素,如果nums[a]nums[m-a]同时存在,那就直接输出,结束程序。(后面即便有满足和为m的整数对,它的第一个元素的值只会更大)
  • 注意对于每一个存在的nums[a],再去判断nums[m-a]是否存在之前,需要nums[a]--,就相当于你已经把a从所有数字拿出来了,所以它的总次数要减1,然后再去剩下的元素中找和他配对的部分。判断过程结束后,nums[a]++,恢复它的出现次数,因为进行下一次判断时我们会选取另一个元素,所以在此之前要恢复原数组。

代码

#include <iostream>
using namespace std;

int coins[1001];

int main() {
    int n, m, x;
    cin >> n >> m;
    while (n-- > 0) {
        cin >> x;
        // 每个硬币出现的次数,正好实现按面值排序
        coins[x]++;
    }
    // 每个硬币最大面值是500
    // 按面值从小到大
    for (int i=  0; i <= 500; ++ i) {
        // 这个面值存在
        if (coins[i]) {
            // 选用这个硬币,数量-1
            coins[i]--;
            // 这个面值不能超过目标值,缺少部分m-i,若这个面值的硬币存在
            if (m > i && coins[m - i]) {
                // 按从小到大输出这两部分
                cout << i << " " << m - i << endl;
                return 0;
            }
            // 恢复这个硬币数量
            coins[i]++;
        }
    }
    cout << "No Solution";
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 1011 World Cup Betting (20分) 比较大小难度级别

    With the 2010 FIFA World Cup running, football fans the world over were becoming...

    vivi
  • PAT 1016 Phone Bills (25分) sort() + map 逻辑较为复杂

    A long-distance telephone company charges its customers by the following rules:

    vivi
  • PAT 1044 Shopping in Mars (25分) 二分法

    Shopping in Mars is quite a different experience. The Mars people pay by chained...

    vivi
  • Flink是如何kafka读取数据的

    版权声明:本文为博主原创,欢迎转载,转载请标明出处 Blog Address:http://blog.csdn.net/jsjsjs1789 https...

    shengjk1
  • Codeforces Round #633 (Div. 2) A Filling Diamonds (假题,观察)

    You have integer nn. Calculate how many ways are there to fully cover belt-like ...

    glm233
  • hdu---1506(Largest Rectangle in a Histogram/dp最大子矩阵)

    Largest Rectangle in a Histogram Time Limit: 2000/1000 MS (Java/Others)    Memor...

    Gxjun
  • Spring_总结_04_高级配置(二)之条件注解@Conditional

    在上一节,我们了解到 Profile 为不同环境下使用不同的配置提供了支持,那么Profile到底是如何实现的呢?其实Profile正是通过条件注解来实现的。

    shirayner
  • Codeforces Round #622 (Div. 2) A.Fast Food Restaurant

    Tired of boring office work, Denis decided to open a fast food restaurant.

    glm233
  • 不用敲代码也能搭建属于自己的博客。

    偶然的知道了 github page 可以快速搭建博客,并且了解到博客搭建完后,可以不折腾域名和服务器备案,绑定域名后,使用域名访问,和正常搭建的博客也没太大差...

    lillianlin
  • 如何画好软件架构图?为什么说我们需要软件架构图?

    我们尝试通过创建架构图(作为技术文档的一部分)来反映应用程序的内部状态,但大多数时候我们都没能做对。由此产生的架构图可能非常全面,也可能非常模糊。有时,架构图根...

    一个会写诗的程序员

扫码关注云+社区

领取腾讯云代金券