A. Direction Change

解法1:(思维题/递推构造)

思路分析:由题目可知,可以在上下左右四个方向进行移动并且不能在一个方向连续移动两次
即题目本意为:(1)如果不可以保证走到目标位置则返回-1
(2)在可以保证走到目标位置的情况下寻找步数最小的路线
即=>在保证满足在x方向和y方向移动的情况下,减少必要的弥补量

时间复杂度:O(n)
代码描述:

#include<bits/stdc++.h>
using namespace std;
int n;
void solve(){
    int sum=0;
    int a,b;
    cin>>a>>b;
    if(a<b)swap(a,b);
    if((b==1 && a>=3) || (b<1) || (a<1)){
        cout<<-1<<endl;
        return ;
    }
    sum=2*b-2+((a-b)/2*4)+(a-b)%2;
    cout<<sum<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        solve();
    }
   return 0;
}

B. Social Distance

解法1:(思维题)

思路分析:由题目可知,环形桌子坐人,首先将存储获取的每个人对于位置的要求(即左右
至少x个空位)的数组进行排序，然后尽量将这些人排的紧凑的情况下比较所占
空间sum和读入的m的大小进行比较即可得到答案
Tips:注意爆int

时间复杂度:O(NlogN)
代码描述:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e5+10;
int q[N];
int t,n,m;
void solve(){
    cin>>n>>m;
    int sum=0;
    for(int i=0;i<n;i++)cin>>q[i];
    if(n>m){
        cout<<"NO"<<endl;
        return ;
    }
    sort(q,q+n,greater<int>());
    int mark=0;
    for(int i=0;i<n;i++){
        if(i!=n-1)sum+=q[i];
    }
    sum+=q[0]+n;
    if(sum>m)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>t;
    while(t--)solve();
    return 0;
}

C. Make it Increasing

解法1:(贪心/思维题/哈希表)

思路分析:

即题目本意为：你可以对a数组的第i个位置上的值进行乘以任何一个整数(可正可负)加到
b数组的对应的第i个位置,求得为使b数组成为一个递增数组的而对b数组的
操作次数和最小值;
对于b数组每个位置有两种选择
1.a的对应位置乘以一个正数加到b的相应位置
2.a的相应位置乘以一个负数加到b的相应位置
即=>基本思路:(1)在添加的数合法的情况下,选择将这个数改为负数
使得后面的数字有更多的选择余地
又由于为了节省操作的次数,数组中一定会出现0

                 是不是看起来比较晦涩感觉不太靠谱

                       (2)反向验证(1)的思路,假如数组b全为正数则为了节省操作次数
                          第一个数必为0
                          同理,可证b数组全为负数的情况,最后一位必为0亦成立

时间复杂度:O(N^2)
代码描述:

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5010;
int t,n,m,ans;
bool judge=false;
int q[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>q[i];
    for(int i=1;i<=n;i++){
        int sum=0;
        int pos=i;
        int mark=0;
        for(int j=pos-1;j>=1;j--){
            sum+=mark/q[j]+1;
            mark=(mark/q[j]+1)*q[j];
        }
        mark=0;
        for(int j=pos+1;j<=n;j++){
            sum+=mark/q[j]+1;
            mark=(mark/q[j]+1)*q[j];    
        }
        if(!judge)ans=sum,judge=true;
        else ans=min(ans,sum);
    }
    cout<<ans;
}
signed main(){
    ios_base::sync_with_stdio(0);
        solve();
    return 0;
}