题解：B3930 [GESP202312 五级] 烹饪问题

XiaoYang_awa · 2025-01-13 17:22:49 · 题解

B3930 [GESP202312 五级] 烹饪问题

看到题解区大佬好多厉害做法，那本蒟蒻也来献上一篇相对简单的解法！

思路：

第一版：

看到题的第一反应肯定是双层循环打擂台，于是就有了第一版代码：

非正解
#include<bits/stdc++.h>
using namespace std;
int n,maxn=INT_MIN;
int a[1000005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];//输入
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(i==j)continue;//两种食材不能相同
            maxn=max(maxn,a[i]&a[j]);//打擂台找最大值
        }
    }
    cout<<maxn;
} 

很明显这样会超时，那么我们需要在这份代码的基础上优化。

第二版：

首先明确一点，什么样的两个数能按位与的结果尽可能大呢？很显然，两数越大，按位与的结果就可能会更大。

有了这一点，我们就可以给输入的数据排个序了：

bool cmp(int x,int y){return x>y;}//【写主函数外】要从大到小排
sort(a+1,a+1+n,cmp); //【写主函数内】使用自带函数

有些人可能会问：但是就算数据有序了，我们还是要遍历找最大的契合度啊。

所以现在的问题就变成了要知道什么时候就已经找到最大值，不用再遍历了。

举样例1的例子：

• 排完序后是这个样子的：3,2,1。
• 我们开始遍历：
  3. - 我们发现，在找到最大值时，从那一次遍历起后面的所有遍历的结果都呈下降趋势。

举样例2的例子：

• 排完序后是这个样子的：13,10,6,5,2。
• 我们开始遍历：
  3. $...
• 我们发现，再继续下去也不会有超过 8 的契合度了。并且在找到最大值时，从那一次起后面的所有遍历的结果都呈下降趋势。

再举几个例子，我们就会发现：当这一次的契合度小于上一次，那么就说明找到最大值了。因为在 a_i 不变的情况下，a_j 就是影响契合度的唯一因素。只要这一个 a_j\&a_i 的结果小于上一次，那么就说明后面所有更小的数都没有可能更大了。可以证明没有反例。

所以我们只需要开一个变量记录上一次的结果，这一次只要小于上一次就可以就可以结束这一次 j 的遍历，直接开始遍历下一个 i 的情况。

完整代码：

应该是最短解了吧。

请不要抄题解
#include<bits/stdc++.h>
using namespace std;
int n,last=INT_MIN,maxn=INT_MIN,a[1000005];
bool cmp(int x,int y){return x>y;}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n,cmp); 
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int data=a[i]&a[j];//存储结果，方便多次使用
            if(i!=j)maxn=max(data,maxn);
            if(data<last)break;//如果小了，就可以break了
            last=data;//更新
        }
    }
    cout<<maxn;
} 

AC记录

完结散花！