打车

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;
}
    
                

#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);
    }
}

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

  }
  }

//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);
}

}

本套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;
}

#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;
        
}

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;



    }

}

    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找组成当前差值的最小硬币数目，减去即可

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);
        }
    }
}

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)

本套试题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;
}

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);
    }

}

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

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);
        }
    }
}

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