大疆笔试0804第一题和第二题

第一题：

输入：多组测试数据。每组测试数据如下

第一行输入三个整数：N、A、X，分别代表需要解决的bug数量、喝咖啡之后效率提升的倍数、一天最多可以喝掉的咖啡数

第二行输入N个整数，表示在不喝咖啡的情况下解决这些八阿哥所需的时间t1, t2, ..., tN

输出：如果能在八小时内解决这些bug(如果时间为小数，向上取整)，输出解决bug的时间，否则输出0

case:input:

8 2 8

60 60 60 60 60 60 60 60

4 3 3

333 77 100 13

output:

240

175

第二题：

输入：多组测试数据

第一行输入两个整数T、N，分别代表钱数和零食种类数。

接下来的N行，每行输入三个整数ai, bi, ci(1 <= i <= N) ，代表零食的价格、零食的满意度、零食的数量

输出：求出最大满意度

case:input

100 2

1 1 1

100 3

26 100 4

5 1 4

5 2 2

output

306

第三题：单源最短路径问题（迪杰斯特拉算法）用代码实现遇到麻烦题目和测试用例都不记得了。此题略过

贴上第一题和第二题的代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {  int N, A, X;  while (!cin.eof()) {  cin >> N >> A >> X;  int tmp;  int time = 0;  int sum = 0;  for (int i = 0; i < N; ++i) {  cin >> tmp;  sum += tmp;  }  int coffeTime = A * X * 60;  if (coffeTime > sum) {  time = ceil((double)(sum) / (double)A);  }  else {  time = sum - coffeTime + ceil((double)(sum) / (double)A);  }  if (time > 480) {  cout << 0;  }  else {  cout << time;  }  }  return 0;
}

#include"stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct backpack
{  int p;  //价格  int sat;  //满意度
} item[2001];   // 零食列表
int main()
{  int money, num;  int price, satisDegree, curNum;  int i, j;  int c;  cin >> money >> num;             //money表示总钱数，num表示零食的种类  int index = 0;  //拆分后零食的总数 拆分的目的是降低时间复杂度  // 二进制优化的方法  for (i = 1; i <= num; i++)  {  c = 1;  cin >> price >> satisDegree >> curNum;       //price表示价格，satisDegree表示满意度，curNum表示该零食的数量。  while (curNum - c>0)     // 1 2 4 8 (1-15)  {  curNum -= c;  item[++index].p = c*price;  item[index].sat = c*satisDegree;  c *= 2;  }  item[++index].p = price*curNum;  //补充不足指数的差值  item[index].sat = satisDegree*curNum;  }  vector<int> dp(money + 1);   //dp[i]代表钱数为i的时候获得的最大满意度  for (i = 1; i <= index; i++)   //对拆分后的物品进行0-1背包  {  for (j = money; j >= item[i].p; j--)  dp[j] = max(dp[j], dp[j - item[i].p] + item[i].sat);  }  printf("%d/money", dp[money]);  return 0;
}

#大疆##笔试题目##笔经#

全部评论

推荐最新楼层

已删除

第三题，简单的最短路，看下数据不大，用的简单的 Floyd算法就可以过（AC） PS：之前发的贴不知道为什么删除了，本着赛后互相分享，互相讨论的初衷，没啥违规的吧

== 参考代码： #include <string.h> #include <stdio.h> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1005; const int INF = 99999999; int map[maxn][maxn], dist[maxn]; bool visit[maxn]; int N,P,C; void init() //初始化 { int i, j; for(i = 0; i < maxn; i++) { for(j = 0; j < maxn; j++) { if(i == j) map[i][j] = 0; else map[i][j] = map[j][i] = INF; } } } void input() //输入函数 { int vi, vj, cost; while(P--) { scanf("%d %d %d", &vi, &vj, &cost); if(cost < map[vi][vj]) map[vi][vj] = map[vj][vi] = cost; } } void floyd() //Floyd算法 { int i, j, k; for(k = 0; k <=N; k++) //k为中间点 for(i = 0; i <= N; i++) for(j = 0; j <= N; j++) if(map[i][k] + map[k][j] < map[i][j]) map[i][j] = map[i][k] + map[k][j]; } int main() { // freopen("in.txt","r",stdin); while(cin>>N>>P>>C) { init(); input(); floyd(); int sum = 0; for(int i=0; i<C; ++i) { int v;cin>>v; sum+=map[0][v]; } printf("%d\n", sum); } return 0; }