[code] PTA 胡凡算法笔记 DAY028

题目A1037 Magic Coupon

在这里插入图片描述

  • 题意
    根据输入的奖券和产品情况,计算出能获取到的最大收益。每个只能选一次。当乘积是负数的时候需要倒贴钱。

  • 思路
    这里贪心思路很直观,将数字排序之后,正数部分从大的数开始相乘,乘到有一方或者都不为正数为止。对于负数部分就是从小开始乘,乘到不为负数为止即可得到最大收益。

  • Code in C++

#include <cstdio>
#include <algorithm>
#define maxn 100001
int coupon[maxn];
int product[maxn];
int main()
{
    int nc, np;
    scanf("%d", &nc);
    for (int i = 0; i < nc; ++i)
    {
        scanf("%d", &coupon[i]);
    }
    scanf("%d", &np);
    for (int i = 0; i < np; ++i)
    {
        scanf("%d", &product[i]);
    }
    long long sum = 0;
    // 从小到大排序
    std::sort(coupon, coupon + nc);
    std::sort(product, product + np);

    // 正向处理负数
    for (int i = 0, j = 0; i < nc && j < np; ++i, ++j)
    {
        if (coupon[i] < 0 && product[j] < 0)
        {
            sum += coupon[i] * product[j];
        }
        else
        {
            break;
        }
    }

    // 反向处理正数
    for (int i = nc - 1, j = np - 1; i >= 0 && j >= 0; --i, --j)
    {
        if (coupon[i] > 0 && product[j] > 0)
        {
            sum += coupon[i] * product[j];
        }
        else
        {
            break;
        }
    }
    printf("%lld", sum);
    return 0;
}


题目A1067 Sort with Swap(0, i)

在这里插入图片描述

  • 题意
    给出序列,只能进行与0的交换操作,求将序列排为递增序列需要花费的最小次数。

  • 思路
    很简单的想法是将0与它所在位置的数进行交换,但是根据示例给出的数据,会发现交换到中间的时候会出现0到位置0的情况,这个时候就需要将0与另外一个不在位置上的数进行交换然后再进行下面的操作。这里用left来记录除0之外不在正确位置上的个数以判断是否还要继续操作。
    注意:这里0在位置0的情况时,如果要一直重新遍历会出现超时情况,所以需要记录一下目前最小的不在正确位置的序号。

  • Code in C++

#include <cstdio>
#include <algorithm>
#define maxn 100010

int pos[maxn];


int main()
{
    int n;
    scanf("%d", &n);
    int left = n - 1, num;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &num);
        pos[num] = i;
        if (num == i && num != 0 )
        {
            --left;
        }
    }

    int k = 1;  // 存放除0以外当前不在本位上的最小的数
    int times = 0;
    while (left > 0)
    {
        if (pos[0] == 0)
        {
            while (k < n)
            {
                if (pos[k] != k)
                {
                    std::swap(pos[0], pos[k]);
                    ++times;
                    break;
                }
                ++k; // 下次判断初始位置
            }
        }

        while (pos[0] != 0)
        {
            std::swap(pos[0], pos[pos[0]]);
            ++times;
            --left;
        }
    }

    printf("%d", times);
    return 0;
}


小结

第一题做的还挺快的,第二题因为开始看题目的时候没太注意是和0交换,然后思索了一下发现不知道怎么停止。后来看到0之后,思路与现在的思路大致一致,但是没有k这个优化不超时的操作,并且对于是否有序的判断也是用一个函数里面循环实现的。发现这一小节的题目可能到时候都要重新再刷刷。

原文链接:加载失败,请重新获取