Each input file contains one test case. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here 1<= NC, NP <= 105, and it is guaranteed that all the numbers will not exceed 230.
For each test case, simply print in a line the maximum amount of money you can get back.
4<br/>1 2 4 -1<br/>4<br/>7 6 -2 -3
43
#include <algorithm> #include <iostream> using namespace std; bool cmp(long long a,long long b){ return a>b; } long long a[100010],b[100010],sum=0; int main(){ int x,y; cin>>x; for(int i=0;i<x;i++) cin>>a[i]; cin>>y; for(int i=0;i<y;i++) cin>>b[i]; sort(a,a+x,cmp); sort(b,b+y,cmp); int num=0,j=0,k=0; while(a[j]>0&&b[k]>0&&num<=x&&num<=y){ sum+=a[j]*b[k]; num++; j++;k++; } j=x-1;k=y-1; while(a[j]<0&&b[k]<0&&num<=x&&num<=y){ sum+=a[j]*b[k]; num++; j--;k--; } cout<<sum; return 0; }
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; typedef long long LL; int c[N],p[N]; int main(){ int n,m; LL ans = 0; scanf("%d",&n); for(int i = 0; i < n; i++) scanf("%d",&c[i]); scanf("%d",&m); for(int i = 0; i < m; i++) scanf("%d",&p[i]); sort(c,c+n),sort(p,p+m); for(int i = 0; i <n&&i<m&&c[i]<0&&p[i]<0; i++) ans += (LL)c[i]*p[i]; for(int i = n-1,j = m-1; i>=0&&j>=0&&c[i]>0&&p[j]>0;i--,j--) ans += (LL)c[i]*p[j]; printf("%lld\n",ans); }
本题遇到的一个坑,就是int改为long long,不然会越界,如果你不写的话,pat也可以通过,这里过不了。还有一个超时的坑,一开始每次循环我都排序,然后我用了四个索引,完美解决了已经计算过的数据问题,也不会超时,只要排序一次。具体是:int cfirst = 0,clast=N1-1,pfirst=0,plast=N2-1;
#include<iostream>
#include<string>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int N1,N2;
scanf("%d",&N1);
long long *coupons = new long long[N1];
for(int i=0;i<N1;i++)
{
long long tmp1;
cin>>tmp1;
coupons[i] = tmp1;
}
scanf("%d",&N2);
long long *productvalue = new long long[N2];
for(int i=0;i<N2;i++)
{
int tmp2;
cin>>tmp2;
productvalue[i]=tmp2;
}
long long sum = 0;
sort(coupons,coupons+N1);
sort(productvalue,productvalue+N2);
int cfirst = 0,clast=N1-1,pfirst=0,plast=N2-1;
while(1)
{
if(cfirst>clast||pfirst>plast)
{
break;
}
long long maxN = coupons[clast]*productvalue[plast];
long long minN = coupons[cfirst]*productvalue[pfirst];
if(maxN<minN)
{
if(minN<=0)
{
break;
}
sum+=minN;
cfirst++;
pfirst++;
}else
{
if(maxN<=0)
{
break;
}
sum+=maxN;
clast--;
plast--;
}
}
cout<<sum<<endl;
return 0;
}
//测试用例无问题,只是牛客的测试数据太大了。。。记得都要用long import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int az,bz; int m=in.nextInt(); long a[]=new long[m]; for(int i=0;i<m;i++){ a[i]=in.nextLong(); } int n=in.nextInt(); long b[]=new long[n]; for(int i=0;i<n;i++){ b[i]=in.nextLong(); } Arrays.sort(a); Arrays.sort(b); for(int i=0;;i++){ if(a[i]>0){ az=i;break; } } for(int i=0;;i++){ if(b[i]>0){ bz=i;break; } } long sum=0; for(int i=0;i<az&&i<bz;i++){ sum+=a[i]*b[i]; } for(int i=m-1,j=n-1;i>=az&&j>=bz;i--,j--){ sum+=a[i]*b[j]; } System.out.println(sum); } }
#include <cstdio> #include <algorithm> using namespace std; int main(void){ int nc; scanf("%d", &nc); long long cou[100005]; for(int i = 0; i < nc; i++){ scanf("%lld", &cou[i]); } int np; scanf("%d", &np); long long pro[100005]; for(int i = 0; i < np; i++){ scanf("%lld", &pro[i]); } sort(cou, cou + nc); sort(pro, pro + np); long long res = 0; int p = 0; while(p < nc && p < np && cou[p] < 0 && pro[p] < 0){ res += cou[p] * pro[p]; p++; } int q = np - 1; p = nc - 1; while(p >= 0 && q >= 0 && cou[p] > 0 && pro[q] > 0){ res += cou[p] * pro[q]; p--; q--; } printf("%lld", res); return 0; }//牛客的数据太大,全用long long,scanf也别忘了 %lld
#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); int n,m; long long x; vector<long long> v1,v2,v3,v4; cin>>n; for(int i=0; i<n; i++) { cin>>x; if(x>0) { v1.emplace_back(x); } else if(x<0) { v2.emplace_back(x); } } cin>>m; for(int i=0; i<m; i++) { cin>>x; if(x>0) { v3.emplace_back(x); } else if(x<0) { v4.emplace_back(x); } } sort(v1.rbegin(),v1.rend()); sort(v2.begin(),v2.end()); sort(v3.rbegin(),v3.rend()); sort(v4.begin(),v4.end()); int l1=v1.size(),l2=v2.size(),l3=v3.size(),l4=v4.size(); l1=min(l1,l3); l2=min(l2,l4); long long sum=0; for(int i=0;i<l1;i++){ sum+=v1[i]*v3[i]; } for(int i=0;i<l2;i++){ sum+=v2[i]*v4[i]; } cout<<sum; return 0; }
a = int(input()) a = list(map(int,input().split())) m = sorted(list(filter(lambda x:x > 0,a)),reverse = True) n = sorted(list(filter(lambda x:x < 0,a))) b = int(input()) b = list(map(int,input().split())) p = sorted(list(filter(lambda x:x > 0,b)),reverse = True) q = sorted(list(filter(lambda x:x < 0,b))) c = 0 for i in range(min(len(m),len(p))): c += m[i] * p[i] for i in range(min(len(n),len(q))): c += n[i] * q[i] print(c)
为了使和最大,正数乘正数,负数乘负数,在牛客数据比较厉害,用long long
#include<iostream> #include<stdlib.h> #include<algorithm> #include<vector> typedef long long LL; using namespace std; bool com(int a,int b) { return a > b; } int main() { vector<LL> con,pro; LL n = 0, m = 0, tem = 0, sum = 0; cin >> n; for (int i = 0; i < n; i++) { cin >> tem; con.push_back(tem); } cin >> m; for (int i = 0; i < m; i++) { cin >> tem; pro.push_back(tem); } sort(con.begin(), con.end(),com); sort(pro.begin(), pro.end(),com); for (int i = 0,j = 0; i < con.size() && j < pro.size(); i++, j++) {//从开始都是正的算 if ((con[i] > 0 && pro[j] > 0)) { sum += (con[i] * pro[j]); } } for (int i = con.size()-1, j = pro.size()-1; i >=0 && j >=0 ; i--, j--) {//从尾部都是负的算 if (con[i] < 0 && pro[j] < 0) { sum += (con[i] * pro[j]); } } cout << sum << endl; system("pause"); return 0; }
//两个数组从小到大排序 //负数最大乘以负数最大,依次往后。 //正数最大乘以正数最大,依次向前 #include<bits/stdc++.h> using namespace std; int main(){ int nc,np,i,j; long long c[100010],p[100010]; long long sum=0; cin>>nc; for(i=0;i<nc;i++) cin>>c[i]; cin>>np; for(i=0;i<np;i++) cin>>p[i]; sort(c,c+nc); sort(p,p+np); i=0;j=0; while(c[i]<0 && p[j]<0 && i<nc && j<np) sum+=c[i++]*p[j++]; i=nc-1;j=np-1; while(c[i]>0 && p[j]>0 && i>=0 && j>=0) sum+=c[i--]*p[j--]; cout<<sum; return 0; }
#简单来说 就是正数乘正数,负数乘负数 n = input() n = int(n) lst1 = list(map(int,input().split())) lst1P,lst1N = [],[] for i in lst1: if i>=0: lst1P.append(i) else: lst1N.append(i) m = input() m = int(m) lst2 = list(map(int,input().split())) lst2P,lst2N = [],[] for i in lst2: if i>=0: lst2P.append(i) else: lst2N.append(i) if lst1P: lst1P.sort() lst1P.reverse() if lst1N: lst1N.sort() if lst2P: lst2P.sort() lst2P.reverse() if lst2N: lst2N.sort() su = 0 miP = min(len(lst1P),len(lst2P)) miN = min(len(lst1N),len(lst2N)) for i in range(0,miP): su+=lst1P[i]*lst2P[i] for i in range(0,miN): su+=lst1N[i]*lst2N[i] print(su)
思路: 排序后前面的乘完后,乘后面的。 #include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; long long HowMuch(vector<long long> & money, vector<long long> & product) { long long sum = 0; sort(money.begin(), money.end()); sort(product.begin(), product.end()); int ms=0; int me = money.size() - 1; int ps = 0; int pe = product.size() - 1; bool check = true; while(check) { if(ms > me || pe < ps) { break; } if(money[me] * product[pe] > 0) { sum += money[me] * product[pe]; me--; pe--; } else if(money[ms] * product[ps] > 0) { sum += money[ms] * product[ps]; ms++; ps++; } else break; } return sum; } int main() { int nc,np; //ifstream cin("test.txt"); while(cin >> nc) { vector<long long> vc(nc); for(int i=0; i<nc; i++) { cin >> vc[i]; } int np; cin >> np; vector<long long> vp(np); for(int i=0; i<np; i++) { cin >> vp[i]; // cout << endl; } cout << HowMuch(vc, vp) << endl; } }
#include <iostream> #include <vector> #include <algorithm> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; vector<long long> coupons_P; vector<long long> coupons_N; vector<long long> products_P; vector<long long> products_N; long long maxSum = 0; int main(int argc, char** argv) { int NC, NP; cin >> NC; for(int i = 0;i < NC;i++){ long long x; cin >> x; if(x >= 0) coupons_P.push_back(x); else coupons_N.push_back(x); } cin >> NP; for(int i = 0;i < NP;i++){ long long x; cin >> x; if(x >= 0) products_P.push_back(x); else products_N.push_back(x); } sort(coupons_P.begin(),coupons_P.end()); sort(coupons_N.begin(),coupons_N.end()); sort(products_P.begin(),products_P.end()); sort(products_N.begin(),products_N.end()); int lth1, lth2, lth3, lth4, a, b; lth1 = coupons_P.end() - coupons_P.begin(); lth2 = coupons_N.end() - coupons_N.begin(); lth3 = products_P.end() - products_P.begin(); lth4 = products_N.end() - products_N.begin(); a = lth1 < lth3 ? lth1 : lth3; b = lth2 < lth4 ? lth2 : lth4; for(int i = 0;i < a;i++){ maxSum += coupons_P[lth1 - i -1] * products_P[lth3 - i - 1]; } for(int i = 0;i < b;i++){ maxSum += coupons_N[i] * products_N[i]; } cout << maxSum << endl; return 0; }
def sumGroup(g1, g2): l1 = len(g1) l2 = len(g2) l = min(l1, l2) rlt = 0 for i in range(l): rlt += (g1[i]*g2[i]) return rlt nc = input() coupons = raw_input().strip().split() np = input() products = raw_input().strip().split() coupons = map(int, coupons) products = map(int, products) positiveCoupons = filter(lambda x: x>=0, coupons) negativeCoupons = filter(lambda x: x<0, coupons) positiveProducts = filter(lambda x: x>=0, products) negativeProducts = filter(lambda x: x<0, products) positiveCoupons.sort(reverse = True) positiveProducts.sort(reverse = True) negativeCoupons.sort() negativeProducts.sort() rlt = sumGroup(positiveCoupons, positiveProducts) rlt += sumGroup(negativeCoupons, negativeProducts) print(rlt)
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int main() { long na,nb,i,j,a[100001],b[100001],az,bz,sum=0; cin>>na;for(i=0;i<na;i++) cin>>a[i]; cin>>nb;for(i=0;i<nb;i++) cin>>b[i]; sort(a,a+na);sort(b,b+nb); for(i=0;i<na;i++) if(a[i]>0) break;az=i; for(i=0;i<nb;i++) if(b[i]>0) break;bz=i; for(i=na-1,j=nb-1;i>=az&&j>=bz;i--,j--) sum+=a[i]*b[j]; for(i=j=0;i<az&&j<bz;i++,j++) sum+=a[i]*b[j]; printf("%ld\n",sum); return 0; }