文章目錄

• • • 題目分析
    • 題目來(lái)源

題目分析

來(lái)源：acwing

分析: 貪心。

兩個(gè)數(shù)列分別從大到小排列。從前往后遍歷，如果a數(shù)組和b數(shù)組前k個(gè)數(shù)都是正數(shù)，就相乘累加到res中；

從后往前遍歷，如果a數(shù)組和b數(shù)組后m個(gè)數(shù)都是負(fù)數(shù)，將相乘累加到res中。最后輸出res。

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int a[N],b[N]; int main(){int n , m;cin >> n;int res = 0;for(int i = 0; i< n; i++) cin>> a[i];sort(a,a+n,greater<int>());cin>> m;for( int i = 0; i< m ;i++) cin >> b[i];sort(b,b+m,greater<int>());int k1 = 0,k2 =0;while(a[k1]>0) k1++;while(b[k2]>0) k2++;for(int i = 0,j = 0; i<k1 && j<k2;i++,j++)res += a[i]*b[j];for(int i = n-1 ,j =m-1; i>=k1 && j>= k2; i--,j--)res += a[i]*b[j];cout<<res<<endl;}

題目來(lái)源

PAT甲級(jí)1037 Magic Coupon
https://www.acwing.com/problem/content/1523/

總結(jié)

以上是生活随笔為你收集整理的PAT甲级1037 Magic Coupon：[C++题解]贪心的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。