1. 咖啡的香气
题目描述
小杰有N个bug没修，假设每喝一杯咖啡，就能让自己一个小时内的debug效率提升到原来的A倍，一小时内重复喝没用，最多只能喝X杯，每天只能工作8小时，而在没喝咖啡的状态下解决每个bug所需要的时间为t1,t2,...,tN分钟
输入
8 2 8
60 60 60 60 60 60 60 60
4 3 3
333 77 100 13
输出
240
175
#include <iostream>
using namespace std;
int C[105];
int main(){
int N,A,X;
while(scanf("%d%d%d", &N, &A, &X) != EOF){
//cin>>N>>A>>X;
int sum = 0;
for (int i=0; i<N; i++){
cin>>C[i];
sum += C[i];
}
int cost = 0;
if (sum <= X * A * 60){
cost = sum % A ==0?(sum / A):(sum / A)+1;
cout<<cost<<endl;
}else{
cost = sum - X*A*60 + X*60;
if (cost > 8*60){
cout<<"0"<<endl;
}else{
cout<<cost<<endl;
}
}
}
return 0;
}
2. 应该吃哪个呢？
题目描述
小A是一个大吃货，但为了减肥，每次只能买总价格少于V的零食。对于每种零食，有价格v、满意度l、数量c，零食只能整数倍购买，不能买半件，问在有限的价格内小A买到的零食的总满意度最高是多少？
输入
2 10
1 1 1
1 1 1
3 100
26 100 4
5 1 4
5 2 2
输出
2
306
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct node{
int v, l;
}Node;
int dp[10005]={0};
Node C[10005]={0};
int main(){
int N, T;
while(scanf("%d%d", &N, &T) != EOF){
int k=0;
for (int i=0; i<N; i++){
int p1, p2, p3;
scanf("%d%d%d", &p1, &p2, &p3);
while(p3--){
C[k].v = p1;
C[k].l = p2;
k++;
}
}
for (int i=0; i<=T; i++) dp[i] = 0;
for (int i=0; i<k; i++){
for (int j=T; j>=C[i].v; j--){
dp[j] = max(dp[j], dp[j-C[i].v]+C[i].l);
}
}
cout<<dp[T]<<endl;
}
return 0;
}
3. S1机器人
题目描述
比赛场地有N个路标，路标的编号从0到N-1，S1机器人只能沿直线在两个路标之间移动，且规定部分路标之间是不能移动的。
每轮比赛，S1机器人都从编号为0的路标出发，然后裁判给一个随机路标，要求S1以最快的速度到达目标位置，最终总时间最短者获胜。
输入
2 1 1
0 1 10
1
4 5 3
0 1 15
1 2 15
0 3 50
1 3 30
2 3 10
2
1
3
输出
10
85
#include <iostream>
#include <string.h>
using namespace std;
const int INF = 0x7fffffff;
const int size = 201;
int Map[size][size],dist[size];
bool vis[size];
void Dijkstra(int s, int N) ///从原点s到其他N-1个点的距离
{
memset(vis,false,sizeof(vis));///初始化
vis[s]=true;///s到各点距离，所以s已经被访问
for(int i=1; i<=N; i++) ///初始化距离数组
dist[i]=Map[s][i];
for(int i=1; i<=N-1; i++) ///迪杰斯特拉核心语句
{
int minn = INF, u;///辅助变量
for(int j=1; j<=N; j++)
{
if(vis[j]==0&&dist[j]<minn)
{
minn=dist[j];
u=j;
}
}
vis[u]=true;///为已访问
for(int v=1; v<=N; v++)
{
if(Map[u][v]<INF)
{
if(dist[v]>dist[u]+Map[u][v])
dist[v]=dist[u]+Map[u][v];///松弛完成
}
}
}
}
int main(){
int N, P, C;
while(scanf("%d%d%d", &N, &P, &C) != EOF){
for(int i=0; i<=N; i++) ///初始化
{
for(int j=0; j<=N; j++)
{
if(i==j) Map[i][j] = 0;
else Map[i][j] = INF;
}
}
int A, B, T;
for (int i=0; i<P; i++){
cin>>A>>B>>T;
Map[A+1][B+1] = T;
Map[B+1][A+1] = T;
}
Dijkstra(1, N);
int result = 0, target;
for (int i=0; i<C; i++){
cin>>target;
result += dist[target+1];
}
cout<<result<<endl;
}
return 0;
}
