牛客算法周周练7签到题题解

数字比较

思路：签到题，这题应该是高中数学考试基本必考的一题，思路很简单，本来想用矩阵快速幂的，但发现a，b都很大，矩阵快速幂肯定爆，既然会爆掉。然后，我们用对数来转换，开longlong就不会爆了。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int x,y;
    cin>>x>>y;
    ll a=y*log(x);   //巧妙转换，指数换对数
    ll b=x*log(y);
    if(a>b)  cout<<">"<<endl;
    else if(a==b)  cout<<"="<<endl;
    else  cout<<"<"<<endl;
    return 0;
}

收集纸片

思路：我们发现由于坐标的范围比较小，所以可以用暴力枚举法来求解，这里可以利用的是全排列，也就是将这n个纸片所在的点的顺序都进行一次排列，然后，对于每种排列的情况都进行计算依次走过这n个点的距离，取最小的即可。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
}Node[30];
int p[30],mi=1e3;
int n,l,w,a,b;
void calc(){
    int ans=abs(a-Node[p[0]].x)+abs(b-Node[p[0]].y);
    for(int i=1;i<n;i++){   //枚举依次走过这n个点的距离，找出最小值
        ans=ans+abs(Node[p[i]].x-Node[p[i-1]].x)+abs(Node[p[i]].y-Node[p[i-1]].y);
        if(ans>mi)  return;
    }
    mi=min(mi,ans+abs(a-Node[p[n-1]].x)+abs(b-Node[p[n-1]].y));
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>l>>w>>a>>b;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>Node[i].x>>Node[i].y;    
            p[i]=i;
        }
        do{
            calc();
        }while(next_permutation(p,p+n));
        cout<<"The shortest path has length "<<mi<<endl;
    }
    return 0;
}