大虎2021软件校招笔试题

 1.

说明：trip[i][1]为上车点的人数，trip[i][2]为下车点的人数 

#include <iostream>
#include <vector>
using namespace   std;

int minCarCount(vector<vector<int> > trips,int capcity)
{
    vector<int> stations(1001);
    int len=trips.size();
    for(int i=0;i<len;i++){
        for(int j=trips[i][1];j<=trips[i][2];j++){
            stations[j]+=trips[i][0];
        }
    }
    int count=0;
    for(int i=0;i<1001;i++){
       count=max(count,stations[i]);
    }
    int res=count%capcity==0?count/capcity:(count/capcity+1);
    return  res;
}
int main()
{
   int n;
   cin>>n;
   vector<vector<int> > trips(n,vector<int>(3));
   for(int i=0;i<n;i++){
       for(int j=0;j<3;j++){
           cin>>trips[i][j];
       }
   }
   int capcity;;
   cin>> capcity;
   int res= minCarCount(trips,capcity);
   cout<<res;
}

 2.利用回溯思路

   

#include <iostream>
#include <algorithm>
#include <vector>
using namespace  std;
static vector<int> havedone(1) ;
static int findmax(vector<vector<int> >tasks,int level){

    int levmax = 0;
    int use = -1;
    for (int i = 0;i < tasks.size();i++)
    {
        if ( level>=task[i][0] && !havedone[i])
        {
            if (tasks[i][1] >= levmax)
            {
                levmax = tasks[i][1];
                use = i;
            }
        }
    }
    havedone[use] = true;
    return levmax;
}
int maxlevel(int x,int level,vector<vector<int> > task)
{
    int maxlev=0;

    for(int i=0;i<x;i++){
       level +=findmax(task,level);
    }

   return level;
}

int main()
{
   int x;
   int level;
   cin>>x>>level;
  vector<vector<int> > task(3,vector<int>(2));
   for(int i=0;i<3;i++){
      for(int j=0;j<2;j++){
          cin>>task[i][j];
      }
   }
   int res=maxlevel(2,1,task);
   cout<<res;
    return 0;
}