A 牛牛爱奇数

题意：给定一组数，每次可以选择一个偶数，使得所有与相等的数都除以2，问把所有数都变成一个奇数所需要的最小的操作数
题解：按题意模拟即可，把所有数存放到map中，然后反向迭代（比赛中忘了反向迭代怎么用了，浪费半天时间qwq）

class Solution {
public:
    /**
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型vector 代表n个数字的值
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        // write code here
        map<int,int>um;
        int cnt=0;
        for(int i=0; i<n; i++){
           if(a[i]%2==0){
               um[a[i]]++;
               cnt++;
           }
        }
        int ans=0;
        map<int,int>::reverse_iterator i; 
        for(i = um.rbegin(); i!= um.rend(); ++i){ 
            if(i->second!=0){
                ans++;
                if(i->first/2%2==0){
                    um[i->first/2]+=i->second;
                }
                else{
                    cnt-=i->second;
                }
            }
        }
        return ans;
    }
};

B 牛牛摆放花

题意：给定一串数字，问你怎么摆放成一个首尾相连的圆，使得相邻的两数之差最大值最小
题解：很明显可以知道，要想相邻的数之差最小，就要使得两数尽可能的靠近，排序往双端队列两边加数即可

class Solution {
public:
    /**
     * 返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型vector 花的高度数组
     * @return int整型
     */
    int solve(int n, vector<int>& array) {
        // write code here
        deque<int>d;
        sort(array.begin(), array.end());
        int st=1;
        int ans=0;
        for(int i=array.size()-1; i>=0; i--){
            if(st==1){
                if(d.size() > 0){
                    ans=max(ans,d.front()-array[i]);
                }
                d.push_front(array[i]);
            }else{
                ans=max(ans,d.back()-array[i]);
                d.push_back(array[i]);
            }
            st^=1;
        }
        return ans;
    }
};

C 星球游戏

题意：两个人占领n个点的p和q个点，然后问你两个集合的最短路径长度
题解：由于题目限制并且，那么说明不会太大，直接对于跑单源最短路（堆优化），然后找出答案答案

const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
struct node{
    int val,id;
    node(int id,int val):id(id),val(val) {}
    bool operator <(const node &hs)const{
        return val>hs.val;
    }
};
struct edge{
    int next,to,w;
}e[maxn*2];
int head[maxn],cnt;

void addedge(int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}
int dis[maxn],vis[maxn];
void dijkstra(int from,int n){
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
    }
    priority_queue<node>q;
    q.push(node(from,0));
    dis[from]=0;
    while(!q.empty()){
        int cur=q.top().id;
        q.pop();
        if(vis[cur])continue;
        vis[cur]=true;
        for(int i=head[cur]; i ; i=e[i].next){
            int v=e[i].to;
            if(dis[cur]+e[i].w < dis[v]){
                dis[v]=dis[cur]+e[i].w;
                q.push(node(v,dis[v]));
            }
        }
    }
}
class Solution {
public:
    /**
     * 
     * @param niuniu int整型vector 牛牛占领的p个星球的编号
     * @param niumei int整型vector 牛妹占领的q个星球的编号
     * @param path int整型vector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int整型 星球个数n
     * @return int整型
     */
    int Length(vector<int>& niuniu, vector<int>& niumei, vector<vector<int> >& path, int nn) {
        // write code here
        int p=niuniu.size();
        int q=niumei.size();
        vector<int>a;
        vector<int>b;
        if(p>q){
            for(auto i:niumei) a.emplace_back(i);
            for(auto i:niuniu) b.emplace_back(i);
            swap(p,q);
        }else{
            for(auto i:niuniu) a.emplace_back(i);
            for(auto i:niumei) b.emplace_back(i);
        }
        for(auto i:path){
            int x=i[0];
            int y=i[1];
            int z=i[2];
            addedge(x,y,z);
            addedge(y,x,z);
        }
        int ans=INF;
        for(auto i:a){
            dijkstra(i,nn);
            for(auto j:b){
                ans=min(ans,dis[j]);
            }
        }
        if(ans == INF) ans=-1;
        return ans;
    }
};