1. 咖啡的香氣
題目描述
小杰有N個(gè)bug沒修，假設(shè)每喝一杯咖啡，就能讓自己一個(gè)小時(shí)內(nèi)的debug效率提升到原來的A倍，一小時(shí)內(nèi)重復(fù)喝沒用，最多只能喝X杯，每天只能工作8小時(shí)，而在沒喝咖啡的狀態(tài)下解決每個(gè)bug所需要的時(shí)間為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. 應(yīng)該吃哪個(gè)呢？
題目描述
小A是一個(gè)大吃貨，但為了減肥，每次只能買總價(jià)格少于V的零食。對(duì)于每種零食，有價(jià)格v、滿意度l、數(shù)量c，零食只能整數(shù)倍購買，不能買半件，問在有限的價(jià)格內(nèi)小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機(jī)器人
題目描述
比賽場地有N個(gè)路標(biāo)，路標(biāo)的編號(hào)從0到N-1，S1機(jī)器人只能沿直線在兩個(gè)路標(biāo)之間移動(dòng)，且規(guī)定部分路標(biāo)之間是不能移動(dòng)的。
每輪比賽，S1機(jī)器人都從編號(hào)為0的路標(biāo)出發(fā)，然后裁判給一個(gè)隨機(jī)路標(biāo)，要求S1以最快的速度到達(dá)目標(biāo)位置，最終總時(shí)間最短者獲勝。
輸入
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) ///從原點(diǎn)s到其他N-1個(gè)點(diǎn)的距離
{
memset(vis,false,sizeof(vis));///初始化
vis[s]=true;///s到各點(diǎn)距離，所以s已經(jīng)被訪問
for(int i=1; i<=N; i++) ///初始化距離數(shù)組
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;
}
