P9234 [蓝桥杯 2023 省 A] 买瓜 题解

Bamboo_Day

2023-05-15 23:36:53

题解

前言

小木棍子都听说过吧。没错就是小波上课打挂那道

跟这题没多大关系,不过如果你切了小木棍,就会觉得这道题很简单。

讲讲我一开始的思路

第一眼看,排序,然后和埃及分数一样根据后续的瓜全买能不能满足剪枝,然后搜索的时候加个二分寻找当前第一个切开比剩下小的值。

后面发现因为数据水所以加不加二分没差多少

最后清晰的讲述一下我的思路

第一步

先将所有的元素从大到小进行排序,然后做一下后缀和(后面可行性剪枝用)。

第二步,开始搜索。

搜索的时候注意顺序要从前往后搜,也就是说后面被搜到的元素不能大于前面的(这里感性理解一下,如果大的搜了搜小的,然后搜完小的又去搜大的就重复了,排序就没有意义了)。

关于可行性剪枝自然就是用第一步求出的后缀和直接判断一下后面所有的瓜加起来有没有剩下需要的瓜多。

然后就结束了。

关于一些小技巧

可以在读入的时候就把数据乘 2,这样就可以用 long long 存下了(机房大佬说 double 常数很大)。

然后就是把题目看清楚,求的是需要切开的瓜,还有如果不行要输出 -1不然你会因此 WA 一个点

Code

#include <bits/stdc++.h>
#define int long long//记得开 long long 
#define ull unsigned long long

const int N = 1e6+10;
const int M = 1e4+10;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;

using namespace std;
int a[40],n,m,b[40];
bool esmite(int pos,int res){
    return b[pos+1] >= res;
}
int ans = INF;
int find(int x){// STL熟练的可以使用 upper_bound 或者 lower_bound 本蒟蒻这两玩意用法分不清故手写 
    int l = 1, r = n;
    while(l < r){
        int mid = (l+r) >> 1;
        if(a[mid] / 2 <= x){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    return l;
}
void dfs(int num,int rest,int pos){//num 当前切开了几个瓜,rest 还剩下需要多少瓜,pos当前搜到哪个位置了,防止往前搜 
    if(rest == 0){//统计答案 
        ans = min(ans,num);
        return;
    }
    if(!esmite(pos,rest)) return;//可行性剪枝 
    for(int i = max(pos+1,find(rest));i <= n; i++){//当然这里也可以直接pos+1(说过了数据水) 
        if(a[i] / 2 > rest) continue;
        dfs(num+1,rest - a[i] / 2, i);
        if(a[i] > rest) continue;
        dfs(num,rest - a[i], i);
    }
}
signed main(){
    cin >> n >> m;
    m *=2;//乘2小技巧 
    for(int i = 1; i <= n; i++){
        cin>> a[i];
        a[i] *= 2;
    }
    sort(a+1,a+1+n,greater<int>());//排序 
    for(int i = n; i > 0; i--){//后缀和 
        b[i] = b[i+1] + a[i];
    }
    dfs(0,m,0);
    if(ans == INF) cout<< -1;
    else cout << ans;
    return 0;
}

这里建议加剪枝标签.