蓝桥杯 算法提高 求最大值问题

问题描述
　　给n个有序整数对ai bi，你需要选择一些整数对 使得所有你选定的数的ai+bi的和最大。并且要求你选定的数对的ai之和非负，bi之和非负。
输入格式
　　输入的第一行为n，数对的个数
　　以下n行每行两个整数 ai bi
输出格式
　　输出你选定的数对的ai+bi之和
样例输入
5
-403 -625
-847 901
-624 -708
-293 413
886 709
样例输出
1715
数据规模和约定
　　1<=n<=100
　　-1000<=ai,bi<=1000




下面是我写的  只得了24分

import java.util.Arrays;
import java.util.Scanner;

// 算法提高 求最大值
public class Main9 {
public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	int c=sc.nextInt();
	int b[]=new int[c];
	int array[]=new int[b.length*2];
	for(int i=0;i<(array.length);i++){
		array[i]=sc.nextInt();
	}
	for(int i=0;i<b.length;i++){
		b[i]=array[(i+1)*2-1]+array[(i+1)*2-2];
	}
	Arrays.sort(b);
	for (int i : b) {
		System.out.println(i);
	}
	if(c==1)
		if(b[b.length-1]>=0)
			System.out.println(b[b.length-1]);
			else System.out.println();
	else
	if(b[b.length-1]>=0&&b[b.length-2]>=0)
	System.out.println(b[b.length-1]+b[b.length-2]);
	else System.out.println();
}
}

11 个解决方案

#1

老兄，你是在根据长度判断大小么


这个题目只要是考察有序数对：所以应该是：
凡是ai>=500或者bi<=-500的数对都不用考虑，直接抛弃。

#2

再说你排什么序呀，直接用一个临时变量存储最大值，然后把剩下符合条件的数对和跟-1000和1000比较，再跟它比较大小不就行了

#3

引用 2 楼 fornetuse123的回复:

再说你排什么序呀，直接用一个临时变量存储最大值，然后把剩下符合条件的数对和跟-1000和1000比较，再跟它比较大小不就行了

我的这个可以符合了3个例子，就是有的不符合，不知道是为啥

#4

引用 2 楼 fornetuse123的回复:

再说你排什么序呀，直接用一个临时变量存储最大值，然后把剩下符合条件的数对和跟-1000和1000比较，再跟它比较大小不就行了

排序之后最后一个就是最大值，第二次之。然后两者相加可以得到题目要求的最大值

#5

引用 4 楼 SVDJASFHIAU 的回复:

Quote: 引用 2 楼 fornetuse123的回复:

再说你排什么序呀，直接用一个临时变量存储最大值，然后把剩下符合条件的数对和跟-1000和1000比较，再跟它比较大小不就行了

排序之后最后一个就是最大值，第二次之。然后两者相加可以得到题目要求的最大值

-1000<=ai,bi<=1000我理解错了，我以为是-1000<=ai+bi<=1000了
那你这样求出所有的和，然后再排序，简直最慢的算法了

你完全可以通过比较ai和a(i+1)的大小;并且根据bi和b(i+1)的大小，来决定需不需要进行加法运算，同时获得一个临时最大值。

你要知道，排序的时间复杂度太高了，n的平方。所以轻易不要排序，因为它只需要一个最大值，而没有要求你排序

#6

算了吧，我还33分呢。不看你的了

#7

楼主可以加我qq421672072，我也在刷题，Java组，蓝桥杯决赛

#8

哈哈！！！！！

#9

引用 8 楼 thunderstorm0的回复:

哈哈！！！！！

求帮忙…………………………

#10

45分的在这


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int x[110],y[110];
int dfs(int sumx,int sumy,int s)
{

    int sum=0;
    if(s==0)
    {
        if(sumx+x[s]>=0&&sumy+y[s]>=0&&x[s]+y[s]>0)//最后一层
            sum=x[s]+y[s];
        else
            sum=0;
    }
    else if(x[s]+y[s]>0&&sumx+x[s]>=0&&sumy+y[s]>=0)
        sum=max(dfs(sumx,sumy,s-1),dfs(sumx+x[s],sumy+y[s],s-1)+x[s]+y[s]);
    else
        sum=dfs(sumx,sumy,s-1);
    return sum;
}
int main()
{
    int a,b;

    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    dfs(0,0,n);
    int ans=dfs(0,0,n);
    cout<<ans<<endl;
    return 0;
}

#11

#include<stdio.h>
#include<iostream>
using namespace std;

int a[110],b[110];
int dp[][]

int n;
int m=0;

void dfs(int s,int l,int ai,int bi)
{
if(l==n)
{
if(s>m&&ai>=0&&bi>=0)
m=s;
return;
}
dfs(s,l+1,ai,bi);
dfs(s+a[l]+b[l],l+1,ai+a[l],bi+b[l]);

}

int main()
{
cin>>n;
int ai=0,bi=0,s=0;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i];
if(a[i]>=0&&b[i]>=0)
{
ai+=a[i];
bi+=b[i];
s=s+a[i]+b[i]; 
i--;
n--;
}
if(a[i]<0&&b[i]<0)
{
i--;
n--;
}
}
dfs(s,0,ai,bi);
cout<<m;
return 0;
 } 



66 分的在这