Taro's Shopping

Taro's Shopping

时间: 1ms        内存:128M

描述:

Mammy决定给Taro带来他的第一次购物体验。Mammy告诉他从购物目录中列出的那些中选择他想要的任何两件物品,但是Taro无法决定哪两件,因为所有物品看起来都很吸引人。因此,他计划购买价值最高的两件物品,不超过Mammy允许的金额。由于获得两个相同的物品很无聊,他想要两个不同的物品。 
你被要求帮助Taro选择这两个物品。给出了所有物品的价目表。在列表中的两个物品对中,找到最高价格总和不超过允许金额的对,并打印总和。买两件,不是一件,也不是三件,也不是更多。请注意,列表中的两个或多个物品的定价可能相同。

输入:

输入由多个数据集组成,每个数据集采用以下格式。 
n  m 
a1 a2 ... an 
数据由两行组成。在第一行中,给出了物品数n和允许的最大支付额m.n 是2≤n≤1000的整数.m是满足2≤m≤2,000,000的整数。在第二行中,给出了n个物品的价格。ai(1≤i≤n)是第i个物品的价格。该值是大于或等于1且小于或等于1,000,000的整数。 
输入的结尾由包含两个零的行指示。所有数据集的n的总和不超过50,000。

输出:

对于每个数据集,找到最高价格总和不超过允许量m的两件物品,并在一行中输出总和。如果每对项目的价格总和都超过m,则输出NONE。

示例输入:

3 45
10 20 30
6 10
1 2 5 8 9 11
7 100
11 34 83 47 59 29 70
4 100
80 70 60 50
4 20
10 5 10 16
0 0

示例输出:

40
10
99
NONE
20

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)&&n!=0&&m!=0)
    {
        int i,j,t=0;
        int max=0,sum;
        int a[1001];
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<n;i++)
            for(j=i+1;j<n;j++)
        {
            sum=a[i]+a[j];
            if(sum>max&&sum<=m)
            {
                max=sum;
                t=1;
            }
        }
       if(t)
        printf("%d\n",max);
       else
        printf("NONE\n");
    }
      return 0;
}

参考答案(时间最优[2]):

#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int MAX=5e4+5;
const int inf=2147483647;
int n,m,flag,sum;
int a[MAX];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    while(cin>>n>>m&&(n||m)){
        flag=0;
        sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if((a[i]+a[j])<=m){
                    sum=max(a[i]+a[j],sum);
                    flag=1;
                    break;
                }
            }
        }
        if(flag)cout<<sum<<endl;
        else cout<<"NONE\n";
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注