大疆笔试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
1 1 1
100 3
26 100 4
5 1 4
5 2 2
output
2
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;
}
#大疆##笔试题目##笔经#
== 参考代码：
#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;
}
