2025/1/11 第25场蓝桥入门赛 题解

A: 哪来的AC   :  题目链接

水题：31画

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  cout<<31;
  return 0;
}

B: 酒店安排   : 题目链接

 思路：从大到小排序，求每两个相邻房间的差值  ， 滑动窗口求m-1个差值最小，即为答案

要想最大距离最小化，就要连续住在一起

#include <bits/stdc++.h>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int n,m;
  cin>>n>>m;
  vector<int> nums(n);
  for(int i=0;i<n;i++)
  {
      cin>>nums[i];
  }

  sort(nums.rbegin(),nums.rend());
    
  vector<int> ans;
  for(int i=0;i<n-1;i++)
  {
      ans.push_back(nums[i]-nums[i+1]);
  }

int res=0;
for(int j=0;j<m-1;j++)
{
    res+=ans[j];
}

int t=res;
for(int i=m-1,k=0;i<ans.size();i++,k++)
{
    t = t-ans[k]+ans[i];
    res = min(res,t);
}

  cout<<res<<endl;
  return 0;
}

C ： 男女搭配  ： 题目链接

思路：先计算最多能匹配几组（z)，再判断剩下的人数（p)是否能满足k人；

如果能，直接输出z;

如果不能，计算 k-p  看还需要拆散几组（3人一组），再拿z减去需要拆散的组。

纯暴力会超时！  

#include <bits/stdc++.h>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int t=0;
  cin>>t;
  int n,m,k;
  while(t--)
  {
      cin>>n>>m>>k;

      int z=min(n/2,m);   //最多几组
      
      int p=n-z*2 + m-z;
      if(p < k)
      {
        int w=(k-p)/3;  //需要几组
        if((k-p)%3)w++;
        z-=w;
      }
      
      cout<<z<<endl;
  }
  return 0;
}

D : 排列高手  ： 题目链接

思路：找规律，数学题。    首先理解什么是子数组，一定要是连续的数字。

每次把1排在第一位，2排在最后。

当子数组只有一个数字时（即每个数字）： 除了单独的1，mex是2 ，  其他都是mex都是1

 mex = 2+（n-1)  

当是本身时： mex = n+1   (1~n都有了）

当子数组包含1时： mex都是2   ,  有n-2个这种组合   mex = 2*(n-2)   

当不包含1时：  mex都是1 ， 有 1+ 2 + ...... +(n-1)   种    ,等差数列求和 mex = (n-2)*(n-1)/2

全部情况相加 ： mex = 4*n - 2 + (n-2)*(n-1)/2           ! 注意long long

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    cout << 4 * n - 2 + (n - 2) * (n - 1) / 2 << endl;
    return 0;
}

E : 混乱的草稿纸 ： 题目链接

 思路： 先反转数组，则要求变为大的在前

从n开始统计：   n  ->   n-1  之间有多少个数，这些数都是要放后面的（都是小数）

n依次递减，把之间的数累加，即可

#include <bits/stdc++.h>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int n;
  cin>>n;

  vector<int> nums(n);

int pos=0;
  for(int i=0;i<n;i++)
  {
      cin>>nums[n-i-1];
      if(nums[n-i-1] == n)pos=n-i-1;
  }

int ans=pos;
int k=n-1;
for(int i=pos+1;i<n;i++)
{
    if(nums[i] == k)k--;
    else ans++;
}

cout<<ans<<endl;
  return 0;
}

F : 完美数对  题目链接

思路： map会依据键值key 从小到大排序

if(a2 > b1)break;    //小到大排序，a2已经大了，后面肯定也大     ,提前结束
if(b2 >= a1)ans++;   //条件：b1>=a2 && b2>=a1

！纯暴力，不提前break会超时

#include <bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  // 请在此输入您的代码
  int n=0;
  cin>>n;

  int nums;
  map<int,int> hash;   //自动小到大排序

  for(int i=0;i<n;i++)
  {
      cin>>nums;
      hash[nums]++;   //个数
  }

  int ans=0;
    
  for(auto &[a1,b1]:hash)
  {
      for(auto &[a2,b2]:hash)
      {
          if(a2 > b1)break;    //小到大排序，a2已经大了，后面肯定也大
          if(b2 >= a1)ans++;   //条件：b1>=a2 && b2>=a1
      }
  }
  
  cout<<ans<<endl;
  return 0;
}