阿里笔试4.8
//第二题:地图问题,在n*n地图上,从左上角出发,每次沿着上下左右任意方向移动距离小于k,移动位置需要价值高于当前位置价值。求路上的最大累计价值 #include <iostream> #include <fstream> #include <queue> #include <tuple> using namespace std; //用广度优先搜索,由于下次节点值比本次大,所以无需用mark矩阵记录走过位置。 //状态节点包括(x,y,fees) 前两个是坐标,第三个是累计花销,并在入队列处滚动刷新最大花销值 int main(){ ifstream fin("input.txt"); int A[100][100]; int n,k; fin>>n>>k; //读入矩阵 for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ fin>>A[i][j]; } } int maxfees=0; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; queue<tuple<int,int,int>> q; q.push(make_tuple(0,0,A[0][0])); while(!q.empty()){ auto item=q.front();q.pop(); int x=get<0>(item); int y=get<1>(item); int fees=get<2>(item); maxfees=max(maxfees,fees); for(int d=0;d<4;d++){ int nx=x;int ny=y; for(int tk=k;tk>0;tk--){ nx=nx+dx[d];ny=ny+dy[d]; if(0<=nx && nx<n && 0<ny && ny<n &&A[nx][ny]>A[x][y]){ int nfees=fees+A[nx][ny]; q.push(make_tuple(nx,ny,nfees)); } } } } cout<<maxfees; }
编了个测试样例:
5 3
2 3 5 4 11 2 6 3 1
1 2 7 3 1
1 2 8 3 1
1 2 9 3 1
第一题
某人有n次机会攻击m个怪兽。攻击时,可以一次攻击b只怪兽。每个怪兽有a滴血,每次攻击能让b只怪兽都减一。给定nmab后,最多能消灭多少只怪兽
贪心即可,和电池使用问题类似
#include <iostream> using namespace std; int main(){ int n,m,a,b; cin>>n>>m>>a>>b; if(b>m){ cout<< (n >=a? n:0); }else{ int res=n*b/a; cout<< (res > m? m:res); } }
样例:
5 2 5 2