第一题主要先除以a,b公约数,然后去遍历Y的值就好了
long A, B, a, b; long __algo_gcd(long x, long y) { do { long t = x % y; x = y; y = t; } while (y); return x; } int main(){ while(cin>>A>>B>>a>>b){ long gcd = __algo_gcd(a, b); a /= gcd; b /= gcd; bool status = false; for(long i=B/b; i>=1; i--){ // cout<<i<<endl; if (i*a <= A && i*a>=1) { cout<<(i*a)<<" "<<i*b <<endl; status = true; break; } } if (!status) cout<<"0 0"<<endl; } }第二个有没有大佬来分享一下思路,我的理解是两个节点中所有路径的最大边的最小值,用dijkstra算法的变形,将dist[i,j] = min(dist[i,j], max(dist[i, k], graph[k,j])),假设dist 中存的就是i到j的距离最大边的最小,那么每次更新的时候只需要判断i到k的距离和k-j这边的最大值(即符合路径中最大边)和当前i-j距离取小的那个,但是还是失败了...有没有大佬补充一下思路,40分钟全磕上面了
全部评论
(6) 回帖