Java实现蓝桥杯算法提高双十一抢购

试题算法提高双十一抢购

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　一年一度的双十一又来了，某网购网站又开始了半价销售的活动。

　　小G打算在今年的双十一里尽情地购物，以享受购买的极度快感，她已经列好了她想买的物品的列表。

　　当然小G并不是出身富贵家庭，所以她网银里的钱只是一个有限的整数S（单位：元）。

　　这次抢购她打算遵循这三个原则选择每一个物品：

　　1.先买能“赚”最多的；

　　2.在“赚”一样多的情况下，先买最便宜的（这样买的东西就可能更多了）；

　　3.在前两条里都判断不了购买顺序的话，先购买在列表里靠前的。

　　（由于网站里还是有一部分商品并没有打五折，所以2的情况（“赚”的钱数为0）是完全可能发生的）

　　现在，在双十一的这一天，你要帮小G编写一个程序，来看看她应该去买她列表里的哪些物品。（总价格不要超过S哦）

　　要是帮她写好这个程序的话，或许你能在光棍节这一天里赢得她的芳心哦~

输入格式

　　输入共N+1行。

　　第一行包含两个整数S和N，S表示小G的可用金额，N表示她看上的物品个数。

　　接下来N行，对应每一个物品，每行有两个整数a和b，a是物品的原价（单位：元），b为0或1，若b为0，则此物品不半价，若b为1，则此物品半价销售。

输出格式

　　输出共一行，为小G要买的物品序号（从1开始），用空格隔开，注意按序号从小到大输出。

　　若小G一件都买不了，则输出0.

样例输入

10 3

5 0

4 0

10 1

样例输出

2 3

样例输入

10 3

11 0

21 1

100 1

样例输出

0

数据规模和约定

　　0<S<=10000,0<N<=1000,每一个a和b满足0<a<=1000且b=0或1。

package com.company;

import java.util.Arrays;

import java.util.Scanner;

public class 双十一抢购 {

    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        //sum表示小G的可用金额

        double sum=sc.nextDouble();

        //N表示她看上的物品个数

        int N=sc.nextInt();

        //创建所有商品的集合

        Goods []arr=new Goods[N];

        //给商品赋值

        for(int i=0;i<N;i++){

            arr[i]=new Goods();

            arr[i].price=sc.nextDouble();

            arr[i].off=sc.nextInt();

            arr[i].num=i+1;

        }

        //按照下面这种方式排序

        for(int i=0;i<N-1;i++){

            for(int j=i+1;j<N;j++){

                if(arr[i].price*arr[i].off<arr[j].price*arr[j].off){//先买能“赚”最多的

                    Goods temp;

                    temp=arr[j];

                    arr[j]=arr[i];

                    arr[i]=temp;

                }

                else if(arr[i].price*arr[i].off==arr[j].price*arr[j].off){

                    if(arr[i].price>arr[j].price){//在“赚”一样多的情况下，先买最便宜的

                        Goods temp;

                        temp=arr[j];

                        arr[j]=arr[i];

                        arr[i]=temp;

                    }

                    else if(arr[i].price==arr[j].price){

                        if(arr[i].num>arr[j].num){

                            //在前两条里都判断不了购买顺序的话，先购买在列表里靠前的

                            Goods temp;

                            temp=arr[j];

                            arr[j]=arr[i];

                            arr[i]=temp;

                        }

                    }

                }

            }

        }

        //创建一个结果的数组，进行存储要购买的序号

        int []result=new int[N];

        //用来存储商品的数目

        int count=0;

        //按照刚才排号的顺序，进行购买

        for(int i=0;i<N;i++){

            double realPrice=arr[i].price-arr[i].price*arr[i].off*0.5;

            if(realPrice<=sum){

                sum-=realPrice;

                result[count]=arr[i].num;

                count++;

            }

        }

        //如果没有商品的话，就输出0，结束程序

        if(count==0){

            System.out.print(0);

            System.exit(0);

        }

        //给商品号进行排序

        Arrays.sort(result);

        for(int i=0;i<N;i++){

            if(result[i]!=0){

                System.out.print(result[i]+" ");

            }

        }

    }

    //创建一个商品的类

    public static class Goods{

        int num;//序号

        double price;//原价

        int off;//折扣

        public Goods(){

            num=0;

            price=0;

            off=0;

        }

    }

}

巴特西

Java实现蓝桥杯算法提高双十一抢购

试题算法提高双十一抢购

最新文章

热门文章

巴特西

Java实现 蓝桥杯 算法提高 双十一抢购

试题 算法提高 双十一抢购

最新文章

热门文章

Java实现蓝桥杯算法提高双十一抢购

试题算法提高双十一抢购