2 svdjasfhiau SVDJASFHIAU 于 2016.04.03 22:10 提问

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

问题描述
  给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分

 public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        List<String> lis1=new ArrayList<String>();
        List<String> lis2=new ArrayList<String>();
        int n=sc.nextInt();
        int m=sc.nextInt();
        for(int i=0;i<n;i++){
            lis1.add(sc.next());
        }
        int f=m*2;
        for(int i=0;i<f;i++){
            String s=sc.next();
            if(s.equals("ADD"))f+=1;
            lis2.add(s);
        }
        for(int i=0;i<lis2.size();i++){
            if(lis2.get(i)!=null){
            if(lis2.get(i).equals("DEL")){
                lis1.remove(lis2.get(i+1));
            }
            if(lis2.get(i).equals("ADD")){
                lis1.add(lis1.indexOf(lis2.get(i+1)),lis2.get(i+2));
            }
            }
        }
        System.out.println(lis1.size());
        for (String string : lis1) {
            System.out.print(string+" ");
        }
    }

3个回答

devmiao
devmiao   Ds   Rxr 2016.04.06 17:12
 #include<iostream>
using namespace std;
int a[100],b[100],n;
int res;
int dp(int x,int y,int n)
{
int ret;
if(n==0)
if(x+a[n]>=0&&y+b[n]>=0&&a[n]+b[n]>0)
ret=a[n]+b[n];
else
ret=0;
else if(a[n]+b[n]>0&&x+a[n]>=0&&y+b[n]>=0)
ret=max(dp(x,y,n-1),dp(x+a[n],y+b[n],n-1)+a[n]+b[n]);
else
ret=dp(x,y,n-1);
return ret;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i]>>b[i];
res=dp(0,0,n-1);
cout<<res;
}
SVDJASFHIAU
SVDJASFHIAU 没学过C语言,只懂JAVA
一年多之前 回复
qq_38077079
qq_38077079   2017.03.26 23:39

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();

int[][] number = new int[n][3];
for(int i=0;i<n;i++){
for(int j=0;j<2;j++){
number[i][j] = input.nextInt();
}
number[i][2] = number[i][0]+number[i][1]; //[ai][bi][ai+bi]
}
//按[ai+bi]的大小将数组number进行排序
for(int i=0;i<=n-2;i++){
int k=i;
for(int j=i+1;j<=n-1;j++){
if(number[j][2]<number[k][2])
k=j;
}
if(k!=i){
int m=number[i][2];
number[i][2]=number[k][2];
number[k][2]=m;
}
}

    int sum=0,count=0,sumAi=0;
    for(int i=n-1;i>=0;i--){
        if(number[i][2]>0){
            count++;
            sumAi += number[i][0];
            if(count==1){
                sum += number[i][2];
                if(number[i-1][2]<=0){
                    System.out.println(sum);
                    break;
                }
            }else{
                if(sumAi>=0){
                    sum += number[i][2];
                    if(number[i-1][2]<=0){
                        System.out.println(sum);
                        break;
                    }
                }else{
                    System.out.println(sum);
                    break;
                }
            }
        }else{
            System.out.println(number[i][2]);
            break;
        }
    }   
}

}

SVDJASFHIAU
SVDJASFHIAU   2016.04.03 22:11

public >
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();

}

}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!