首页 > 试题广场 >

打车

[编程题]打车
  • 热度指数:1494 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

妞妞参加完Google Girl Hackathon之后,打车回到了牛家庄。

妞妞需要支付给出租车司机车费s元。妞妞身上一共有n个硬币,第i个硬币价值为p[i]元。

妞妞想选择尽量多的硬币,使其总价值足以支付s元车费(即大于等于s)。


但是如果从妞妞支付的这些硬币中移除一个或者多个硬币,剩下的硬币总价值还是足以支付车费的话,出租车司机是不会接受的。例如: 妞妞使用价值为2,5,7的硬币去支付s=11的车费,出租车司机是不会接受的,因为价值为2这个硬币是可以移除的。


妞妞希望能选取最大数量的硬币,使其总价值足以支付车费并且出租车司机能接受。

妞妞希望你能帮她计算最多可以支付多少个硬币。


输入描述:
输入包括两行, 第一行包括两个正整数n和s(1 <= n <= 10, 1 <= s <= 1000), 表示妞妞的硬币个数和需要支付的车费。
第二行包括n个正整数p[i] (1 <= p[i] <= 100),表示第i个硬币的价值。
保证妞妞的n个硬币价值总和是大于等于s。


输出描述:
输出一个整数, 表示妞妞最多可以支付的硬币个数。
示例1

输入

5 9
4 1 3 5 4

输出

3
1.先排序,定义sum从数组第一个元素累加,到第一次大于等于s停止,
  用cnt记录当前累加个数
2.如果sum刚好等于s,直接返回cnt,如果sum>s,定义dis=sum-s,从累
  加的最后一个元素的前一位开始比较,如果dis大于该元素,dis-=arr[i],
  并且cnt--,直到遍历到第0个位置的元素结束,返回cnt
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n,s;
    cin>>n>>s;
    int * arr = new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    int sum=0,cnt=0,j=0;
    for(int i=0;i<n;i++)
    {
        sum+=arr[i];
        cnt++;
        if(sum<s)
            continue;
        else if(sum==s)
            break;
        else
        {
            j=i-1;
            int dis=sum-s;
            while(j>=0)
            {
                if(dis>arr[j])
                {
                    dis-=arr[j];
                    cnt--;
                    j--;
                }
                else if(dis == arr[j])
                {
                    cnt--;
                    break;
                }
                else
                    j--;
            }
        }
        break;
    }
    cout<<cnt<<endl;
    return 0;
}
    
                

编辑于 2018-03-18 13:46:49 回复(7)
#include<stdio.h>
#include<vector>
using namespace std;
#define max(a,b) a>b?a:b
int main(){
    int n,i,j,v[20],k;
    //freopen("input.txt","r",stdin);
    while(~scanf("%d%d",&n,&k)){
        for(i=0;i<n;i++) scanf("%d",v+i);
        int Max=0;
        for(j=0;j<1<<n;j++){
            vector<int> s;
            int sum=0,flag=1;
            for(i=0;i<n;i++)
                if(j>>i&1) s.push_back(v[i]),sum+=v[i];
            if(sum<k) continue;
            for(i=0;i<s.size();i++)
                if(sum-s[i]>=k){
                    flag=0;break;
                }
            if(flag==1) Max=max(Max,s.size());
        }
        printf("%d\n",Max);
    }
}

发表于 2017-12-30 12:51:28 回复(0)

package NewCode;

import java.util.Scanner;

/**

  • Created by wanyu on 2018/3/19.
    */
    public class L {
    public static void main(String[] args) {
     Scanner cin=new Scanner(System.in);
     int n=cin.nextInt();//硬币数量
     int s=cin.nextInt();//车费
     int corn[]=new int[n+1];
     for(int i=1;i<=n;i++){
         corn[i]=cin.nextInt();
     }
     for(int i=1;i<n;i++){//将硬币从小到大排序
         int min=i;
         for(int j=i+1;j<=n;j++){
             if(corn[min]>corn[j]){
                 min=j;
             }
             }
         if(min!=i){
             int tmp=corn[min];
             corn[min]=corn[i];
             corn[i]=tmp;
         }
     }
     int sum=0;//计算金额
     int i=0;
     boolean flag=false;
     for( i=1;i<=n;i++){
         sum+=corn[i];//从小到大开始累加 确保数量最大
         if(sum==s){//如果等于S 则结束
             break;
         }else if(sum>s){//如果大于S 标记flag进行下一步运算
             flag=true;
             break;
         }
     }
     if(flag){
         int shu=0;
         for(int j=n;j>=1;j--){//从大到小开始减
             if(sum-corn[j]>=s){//如果减掉大金额后仍大于S 则继续
                 sum-=corn[j];
                 shu++;
             }
         }
         i=i-shu;
     }
     System.out.println(i);
    
    }
    }
发表于 2018-03-19 15:44:07 回复(0)

//test
import java.util.Scanner;

public class TaxiCost{
public static void main(String[] args){
//输入
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int total = in.nextInt();
int[] nums =new int[n];
for(int i=0;i<n;i++){
nums[i] = in.nextInt();
}
//排序与计算
sort(nums);
int N = calculatCoin(n,total,nums);
//输出
System.out.print(N);
//结束
in.close();
}

//计算硬币数量
public static int calculatCoin(int n,int total,int[] nums){
    int count =0;
    int sum = 0;
    for(int j=0;j<n;j++){
        sum +=nums[j];
        count++;

        if(sum>=total){
            for(int k=count-1;k>=0;k--){
                if((sum-nums[k])>=total){
                    count--;
                    sum -=nums[k];
                }
            }
            break;
        }        
    }
    //钱不够返回-1,否则返回硬币数量
    return sum<total? -1:count;
}

//排序算法

private static void sort(int[] a){
    sort(a,0,a.length-1);
}    
private static void exch(int[] a,int i,int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}    
private static void sort(int[] a,int lo,int hi){
    if(lo>hi) return;

    int lt=lo,i=lo+1,gt=hi;
    int v=a[lo];

    while(i<=gt){
        if(a[i]>v) exch(a,i,gt--);
        else if(a[i]<v) exch(a,lt++,i++);
        else i++;            
    }        
    //a[lo...lt-1]<=a[lt...gt]<a[gt+1...hi]
    sort(a,lo,lt-1);
    sort(a,gt+1,hi);
}

}

发表于 2018-03-19 12:12:08 回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, s, total=0, count, i;
    cin>>n>>s;
    int data[n];
    for(int i=0; i<n; i++) {
        cin>>data[i];
    }
    sort(data, data+n);
    for(count=0; total<s; count++) {
        total+=data[count];
    }
    for(i=count-1; total>=s&&i>=0; i--) {
        if(total-data[i]>=s) {
            total = total - data[i];
            count--;
        }
    }
    cout<<count;
思路:先按从小到大的顺序排序,之后开始累加到>=s,最后从当前位置开始把可以去掉的硬币去掉。
发表于 2018-03-15 17:35:11 回复(1)
1.排序

2.从小到大累加,>= S 后停止

3.从这个位置倒序搜索,减去第i个硬币仍然大于S就扔掉它,直到总数与S的差值小于最小的硬币


发表于 2018-03-15 12:25:35 回复(0)

本套6道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n, s; cin >> n >> s;
    int data[10] = { 0 };
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    int result = 0;
    for (int i = 0; i < pow(2, n); i++) {
        int mincoin = 10000, sum = 0, sumcoin = 0;
        int temp = i;
        for (int j = 0; j < n; j++) {
            if (temp % 2) {
                sum += data[j];
                mincoin = mincoin < data[j] ? mincoin : data[j];
                sumcoin++;
            }
            temp >>= 1;
        }
        result = sum >= s && sum - mincoin < s ? result>sumcoin ? result : sumcoin : result;
    }
    cout << result;
    return 0;
}
编辑于 2018-03-18 22:13:44 回复(5)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int p[N];
int main(){
    int n,s;
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    sort(p+1,p+n+1);//从小到大排序
    int i=0,cnt=0,sum=0;
    while(sum<s){//累加到刚好大于等于s
        i++;
        cnt++;
        sum+=p[i];
    }
    
    i--;
    while((sum-p[1])>=s){//如果减去最小的数依旧大于等于s
        if((sum-p[i])>=s && i>=1){//就从大到小开始找可以删除的数
            sum-=p[i];
            i--;
            cnt--;
        }else if(i>=1){
            i--;
        }
        
        
    }
    cout<<cnt<<endl;
    return 0;
        
}

发表于 2019-12-01 11:15:41 回复(0)
用01串来枚举
拿样例来说,妞妞有5个硬币,分别价值4 1 3 5 4,需要支付费用为9。
1.可以用一个长度为5的01串来枚举所有的状态,0代表不需要支付这个硬币,1代表需要支付这个硬币,比如01010就代表需要支付第二个硬币和第四个硬币,需要从二进制00000到11111,十进制就是从0到2的n次方-1,因为最多只有10个硬币,所以最多也就是枚举到1023
2.把所有的情况枚举完,去判断哪些情况是合法的,用sum计算当前情况的支付总费用,用cnt计算总共需要支付多少枚硬币。对于当前情况,如果sum小于目标费用s,那么硬币数cnt再多也没用,就忽略这个情况;如果sum>=目标费用s,那么还需要检查一下,如果当前sum减去价值最小的那枚硬币,依旧大于目标费用s,那么就意味着有硬币可以移除,所以这个情况不合理,然后忽略掉,否则的话就更新答案ans=cnt
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long int
#define MIN -1<<30
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
int n,s,ans;
int main()
{
    while(cin>>n>>s)
    {
        ans=MIN;
        for(int i=0;i<n;++i)
        {
            cin>>arr[i];
        }
        sort(arr,arr+n);
        int num=pow(2,n);            //如果身上有n个硬币,那么就有2的n次方种支付情况
        for(int i=0;i<num;i++)       //这些情况可以用二进制表示,枚举所有的情况
        {
            int flag=0,sum=0,cnt=0,t=i;
            for(int j=0;j<n;++j)     //每次计算n个硬币
            {
                if(t&1)              //如果是1代表要用到这个硬币
                {
                    sum+=arr[j];
                    cnt++;
                }
                t/=2;
            }
            t=i;
            for(int k=0;k<n;++k)    //找最小的那个硬币
            {    
                if(t&1)             //找到了
                {
                    if(sum-arr[k]>=s)    //判断是否可以移除最小的金币
                    {
                        flag=1;        
                    }
                    break;
                }
                t/=2;
            }
            
            if(flag || sum<s)
            {
                continue;
            }
            if(cnt>ans)
            {
               ans=cnt;
            }
        }
        cout<<ans<<endl;
    }    
    return 0;
}

发表于 2018-12-18 16:01:33 回复(0)
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int len = sc.nextInt();
            int sum = sc.nextInt();
            int[] coins = new int[len];
            for (int i = 0; i < len; i++) {
                coins[i] = sc.nextInt();
            }
            int res = takeATaxi(coins, sum);
            System.out.println(res);
        }
        sc.close();

    }

    public static int takeATaxi(int[] coins, int sum) {

        Arrays.sort(coins);
        int start = 0;
        int end = 0;
        int temp = 0;
        int res = 0;
        while (end < coins.length) {
            temp += coins[end];
            if (temp >= sum) {
                break;
            }
            end++;
        }
        res = end - start + 1;
        int i = end;
        while(temp >= sum) {
            while (i >= start && temp - coins[i] < sum) {
                i--;
            }
            if(i < 0) {
                break;
            }
            temp -= coins[i];
            res --;
        }
        return res;



    }

}
发表于 2018-05-23 10:43:29 回复(0)
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;

/*该函数是把输入行中的各个整数,存储在int数组中,以备后续使用*/
void LineReturnInt(char *s, int arr[])
{
    char tmp[50] = {0};
    int len = strlen(s);
    int j = 0;
    int start = 0;

    for(int i=0; i<len+1; i++)
    {
        tmp[j] = s[i];
        j++;
        if((s[i] == ' ')||(s[i] == '\0'))
        {
            tmp[j] = '\0';
            arr[start] = atoi(tmp);
            ++start;
            j = 0;
        }
    }
}
int main()
{

    char s[1000];
    int arr[100] = {0};
    int num[100] = {0};

    gets(s);
    LineReturnInt(s, arr);//接收第一行中的两个整数:硬币个数、待付钱数

    gets(s);
    LineReturnInt(s, num);//接收第二行中的多个整数:各个硬币的面值数

    int sum = 0;
    int sum1 =0;
    int count = 0;
    int max = 0;
    int dd = 0;

    for(int i=0; i<arr[0];++i)
    {
        sum = sum + num[i];
        sum1 = sum;
        ++count;

        if(sum1 >= arr[1])
        {

            if(count>max)
            {
                max = count;

                if((sum1-num[i-count+1]) >= arr[1])
                {

                    for(int j=i-count+1; j<arr[0]; ++j)
                    {
                        sum1 = sum1 - num[j];
                        count = count - 1;

                        if(sum1 < arr[1])
                        {
                            if(count<max)
                                max = count+1;
                            break;
                        }
                    }
                }
            }
            sum = sum - num[dd];
            --count;
            ++dd;
        }
    }


    printf("%d\n", max);

    return 0;
}

发表于 2018-04-18 09:59:34 回复(0)
    publicclassMain {
        publicstaticvoidmain(String[] args) {
            Scanner sc = newScanner(System.in);
            intn = sc.nextInt();
            ints = sc.nextInt();
            int[] p = newint[n];
            for(inti = 0; i < n; i++) {
                p[i] = sc.nextInt();
            }
            Arrays.sort(p);
            intcount = 0;
            intii = 0;
            for(intx : p) {
                if(count < s) {
                    count += x;
                    ii++;
                } else{
                    break;
                }
            }
            count -= s;
            int[] dp = newint[count + 1];
            Arrays.fill(dp, count + 1);
            dp[0] = 0;
            for(inti = 1; i <= count; i++) {
                for(intj = 0; j < ii; j++) {
                    if(i >= p[j])
                        dp[i] = Math.min(dp[i], dp[i - p[j]] + 1);
                }
            }
            ii -= dp[count];
            System.out.println(ii);
        }
    }

比较傻瓜的代码, 排序,从小的硬币开始计数,直到当前的硬币总值大于等于s。再减去s, dp找组成当前差值的最小硬币数目,减去即可

发表于 2018-04-07 21:07:30 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        
        int coinNum=sc.nextInt();
        int carMoney=sc.nextInt();
        
        int [] numberInt=new int[coinNum];
        for(int i=0;i<coinNum;i++){
            numberInt[i]=sc.nextInt();
            
        }
        int in,out;
        int temp=0;
        //对取出的值进行冒泡排序
        for (out = numberInt.length; out > 0; out--) {  
            for (in = 0; in < out - 1; in++) {  
                if (numberInt[in] > numberInt[in + 1]) {  
                    temp = numberInt[in];  
                    numberInt[in] = numberInt[in + 1];  
                    numberInt[in + 1] = temp;  
                }  
            }  
        }
        //对硬币数组从小到大进行求和直到大于等于车费为止
        int result=0,tempB=0;
        for(int i=0;i<numberInt.length;i++){
            result++;
            tempB+=numberInt[i];
            if(tempB>=carMoney){
                break;
            }
        }
        //从后往前减去可以减去的硬币数值 ,保证硬币数量最多,又满足题意
        int resultNum=result;
        for(int i=result-2;i>=0;i--){
            if(tempB-numberInt[i]>=carMoney){
                tempB-=numberInt[i];
                result--;
            }
        }
                
        System.out.println(result);
    }
}
发表于 2018-04-03 08:44:01 回复(0)

import java.util.Scanner;

/*
 * 参考大神的解题思路:https://www.nowcoder.com/questionTerminal/893ad8352e21488f8a7c43e1c5bb34e1
 * 使用枚举法,遍历所有可能取到coin的种数,选择更新,参见代码注释
 * */
public class TakingTaxPrice {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int s = scanner.nextInt();
            int[] prices = new int[n];
            for (int i = 0; i < n; i++) {
                prices[i] = scanner.nextInt();
            }

            int count = 0;
//            枚举每种情况
            for (int i = 0; i < Math.pow(2, n); i++) {
                int tmp = i;
                int tmpSum = 0;
                int minCoin = 1001;
                int tmpCount = 0;
                for (int j = 0; j < n; j++) {
//                    如果当前coin被取到
                    if (tmp % 2 != 0) {
                        tmpSum += prices[j];
                        minCoin = Math.min(minCoin, prices[j]);
                        tmpCount++;
                    }
                    tmp >>= 1;
                }
//                满足要求,同时数量变大才进行更新
                if (tmpSum >= s && tmpSum - minCoin < s && tmpCount > count) {
                    count = tmpCount;
                }
            }
            System.out.println(count);
        }
    }
}
编辑于 2018-03-27 14:38:28 回复(1)
def MostCoinsToPay(coins, fee):
    # 快排
    SortedCoins = [int(item) for item in coins]
    fee = int(fee)
    SortedCoins.sort()
    sumCoin = 0
    payCoin = []
    for i in range(len(SortedCoins)):
        coin = SortedCoins[i]
        payCoin.append(coin)
        sumCoin += coin
        if sumCoin >= fee:
            break
    dis = sumCoin - fee
    if dis < 0:
        print('硬币不够支付车费')
    elif dis > 0:
        # 保证 dis >= 0
        i = -2
        while(dis >= 0):
            if dis >= payCoin[i]:
                dis = dis - payCoin[i]
                payCoin.remove(payCoin[i])
            else:
                i -= 1
            if dis < payCoin[0]:
                break
    print(len(payCoin))
if __name__ == '__main__':
    coinNum, fee = input().split(' ')
    coins = input().split(' ')
    MostCoinsToPay(coins, fee)
发表于 2018-03-26 11:07:43 回复(0)

本套试题AC代码在https://github.com/ReyzalX/nowcoder查看

数据很小,直接dfs

#include<bits/stdc++.h>

using namespace std;
int n, s;
vector<int> p;

int result;

void dfs(int cur,int minv,int sum,int count)
{
    if (sum >= s && sum - minv < s) {
        result = max(result, count);
    }
    if (sum > s || cur == n)
        return;
    dfs(cur + 1, min(minv, p[cur]), sum + p[cur], count + 1);
    dfs(cur + 1, minv, sum, count);
}
int main()
{
    cin >> n >> s;
    p.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
    }
    result = -1;
    dfs(0, 0x3d3d3d3d, 0, 0);
    cout << result << endl;
    return 0;
}
发表于 2018-03-26 01:07:02 回复(0)
public class Main {
    public static int a = 0; //存放最长数组长度
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int s = sc.nextInt();
      int p[] = new int[n];
      for(int i =0; i < n; i++){
          p[i] = sc.nextInt();
      }
      Arrays.sort(p);
      List list = new ArrayList();
      for (int i = 1; i<p.length+1; i++) {
          combine(p, 0, i, list, s); //遍历组合
      }
      System.out.println(a);

    }
    public static void combine (int []cs, int begin, int num, List<Integer> list, int s){
        if(num == 0) {
            //当前组合元素的和
            int sum = 0;
            for(int i:list){
                sum = sum +i;
            }
            if((sum >= s) && (sum - list.get(0) < s)) { //如果当前组合元素的和大于所需金额 并且 和减去最小的元素后小于所需金额,则为满足条件的组合
                if(list.size() > a) a = list.size();  //找出最大长度的组合
            }
            return;
        }
        if(cs.length == begin){
            return ;
        }
        list.add(cs[begin]);
        combine(cs, begin+1, num-1, list,s);
        list.remove(list.size()-1);
        combine(cs, begin+1, num, list, s);
    }

}

一个比较笨的方法,列出所有组合,找出满足条件的组合,然后找出最长的组合

编辑于 2018-03-17 17:14:15 回复(0)
import java.util.Scanner;
public class Main {
    private static void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
    // quicksort the subarray a[lo .. hi] using 3-way partitioning
    private static void sort(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        int v = a[lo];
        int i = lo;
        while (i <= gt) {
            int cmp = a[i] - v;
            if (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else i++;
        }
        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }
    public static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int sum = in.nextInt();
            int[] nums = new int[n];
            int total = 0;
            int count = 0;
            for (int i = 0; i < n; i++)
                nums[i] = in.nextInt();
            sort(nums);
            for (int i = 0; i < n; i++) {
                total += nums[i];
                count++;
                if (total == sum) {
                    break;
                } else if (total > sum) {
                    for (int j = count - 1; j >= 0; j--) {
                        if ((total - sum) >= nums[j]) {
                            count--;
                            total -= nums[j];
                        }
                    }
                    break;
                } else
                    continue;
            }
            System.out.println(count);
        }
    }
}
发表于 2018-03-16 09:47:21 回复(0)
var line1=readline().split(" ");
        var a=readline().split(" ").map(x=>parseInt(x,10)).sort(function(a,b){returna-b});
        var n=parseInt(line1[1],10);
        var s=0;
        for(var i=0;s<n;i++){
            s=s+a[i];
        }
        var flag=i;
        for(var j=i-1;s>n&&(j>0);j--){
            if(s-a[j]>=n){s=s-a[j];flag--;}
        }
        print(flag);
发表于 2017-12-26 01:44:43 回复(0)