1037 Magic Coupon (25分)找自己需要的就行,别管那些没用的东西
测试点4超时,把0和边界都考虑到了,应该是算法的原因#include<iostream>#include<vector>#include<algorithm>using namespace std;vector<int> v1,v2;int main(){int m,n,temp,sum=0;scanf("%d",&m);for(int i=
·
测试点4超时,把0和边界都考虑到了,应该是算法的原因。方法没问题,思路又问题,注意简化!
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v1,v2;
int main()
{
int m,n,temp,sum=0;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%d",&temp);
v1.push_back(temp);
}
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&temp);
v2.push_back(temp);
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
while(v1.size()!=0&&v2.size()!=0)
{
if(v1[0]<0||v1[0]==0)
{
if(v1[0]*v2[0]>0)
{
sum=sum+v1[0]*v2[0];
v1.erase(v1.begin());
v2.erase(v2.begin());}
else
v1.erase(v1.begin());
}
else
{
if(v1[v1.size()-1]*v2[v2.size()-1]>0)
{
sum=sum+v1[v1.size()-1]*v2[v2.size()-1];
v1.erase(v1.end()-1);
v2.erase(v2.end()-1);}
else
v1.erase(v1.end()-1);
}
}
printf("%d",sum);
}
看了柳神的,发现我的代码会去搭理那些会使回馈变少的优惠券,甚至还把她们删除,很浪费时间,只要从两端处理,将sum>0的加起来就行。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v1,v2;
int main()
{
int m,n,temp,sum=0;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%d",&temp);
v1.push_back(temp);
}
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&temp);
v2.push_back(temp);
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
int i=0,j=0;
//处理负的优惠券
while(i<m&&j<n&&v1[i]<0&&v2[j]<0)
{
sum+=v1[i]*v2[j];
i++;j++;
}
i=m-1;
j=n-1;
while(i>-1&&j>-1&&v1[i]>0&&v2[j]>0)
{
sum+=v1[i]*v2[j];
i--;j--;
}
printf("%d",sum);
}
更多推荐
已为社区贡献1条内容
所有评论(0)