PAT_甲級_1037 Magic Coupon (25分) (C++)【簽到題/數組】

目錄

​​1，題目描述​​

​​題目大意​​

​​輸入​​

​​輸出​​

​​說明​​

​​2，思路​​

​​3，代碼​​

1，題目描述

Sample Input:

4
1 2 4 -1
4
7 6 -2 -3      

Sample Output:

43      

題目大意

這一題看起來比較繞。。。大緻意思就是，有一個神奇的商店，提供一些“優惠券”，若優惠券為正數k，對某商品使用此券，則可以獲得k倍的補償，若k為負數，則需要多付k倍 的價格。現在需要計算最多可以拿回多少錢 （這操作不愧是在火星上，外婆真的是用心良苦啊。。。）

輸入

1. 第一行：“優惠券”的數目Nc（>1）；
2. 第二行：各優惠券的值；
3. 第三行： 商品的數目Np（<=10^5）；
4. 第四行：商品的價格；

輸出

• 最多可以拿回多少錢；
• 不管是“優惠券”還是商品，都可正可負；

說明

• it is guaranteed that all the numbers will not exceed 2​^30：保證所有數字不會超過2^30；
• 每張券或每份産品最多隻出現一次；

2，思路

以題目所給的例子為準：優惠券{4，2，1，-1}，商品{7，6，-2，-3}； 

3，代碼

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int cmp1(int a, int b){
    return a > b;
}

int main(){
//#ifdef ONLINE_JUDGE
//#else
//    freopen("1.txt", "r", stdin);
//#endif

    int Nc, Np;
    int temp;
    int ans = 0;
    vector<int> coupon, product;
    cin>>Nc;
    for(int i = 0; i < Nc; i++){
        cin>>temp;
        coupon.push_back(temp);
    }
    cin>>Np;
    for(int i = 0; i < Np; i++){
        cin>>temp;
        product.push_back(temp);
    }
    sort(coupon.begin(), coupon.end(), cmp1);
    sort(product.begin(), product.end(), cmp1);

    int index = 0;
    for(index = 0; index < coupon.size() && index < product.size(); index++){   //累加券或商品均為正數的乘積
        if(coupon[index] > 0 && product[index] > 0){
            ans += coupon[index] * product[index];
        }else
            break;
    }
    if(index >= coupon.size() || index >= product.size()){                      //券或者是商品用完了 直接傳回答案
        cout<<ans;
        return 0;
    }       

    int i = coupon.size() - 1, j = product.size() - 1;
    while(i >= 0 && j >= 0){                                                    //累加券或商品均為負數的乘積
        if(coupon[i] < 0 && product[j] < 0){
            ans += coupon[i--] * product[j--];
        }else
            break;
    }


    cout<<ans;

    return 0;
}