当前位置: 代码迷 >> 综合 >> pta--1037 Magic Coupon(25 分)(贪心)
  详细解决方案

pta--1037 Magic Coupon(25 分)(贪心)

热度:23   发布时间:2023-12-26 10:09:50.0

题目:https://pintia.cn/problem-sets/994805342720868352/problems/994805451374313472

【分析】就是将两个序列排序,然后负数和负数相乘,正数和正数相乘,最后求和。

一开始是将两部分放在一起做的,即代码中注释掉的部分。但是总有一个测试点过不了。然后将两个循环分开写了,即都是负数和都是正数的处理分开了,就对了。

注释掉的部分是按顺序来的,但是两个序列的长度不一定是一样的。如果这样的话,会漏掉一部分数据。比如:

-1  1  2  4

-3  -2  6  7  8

如果按注释掉的部分那样,i、j同步向前,那么走到-1×(-2)时也会加上,-3不再处理,但是此时并不是最大值。所以,还是要分开做。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e+5;
int a1[maxn],a2[maxn];
int main()
{int nc,np;scanf("%d",&nc);for(int i=0;i<nc;i++)scanf("%d",&a1[i]);scanf("%d",&np);for(int i=0;i<np;i++)scanf("%d",&a2[i]);sort(a1,a1+nc);sort(a2,a2+np);long long ans=0;int i=0,j;while(i<nc && i<np && a1[i]<0 && a2[i]<0){ans+=a1[i]*a2[i];i++;}i=nc-1;j=np-1;while(i>=0 && j>=0 && a1[i]>0 && a2[j]>0){ans+=a1[i]*a2[j];i--, j--;}
/*********************************************for(int i=nc-1,j=np-1;i>=0,j>=0;i--,j--)if(a1[i]*a2[j]>0)sum+=a1[i]*a2[j];
**********************************************/cout<<ans<<endl;return 0;
}

 

  相关解决方案