美团笔试第三场8.26

分享题解攒人品捏

1，题意：美团可以给树浇水，树成长x点，同时可以施肥，树成长y点，施肥需要间隔2两天，求到z点成长值的最少天数(1e9)

$\qquad$ 假设最少要n天,有 ${n*x} ＋ \lfloor\frac{n}{3}\rfloor*y \ge z$ ，二分或者直接解都可以

2，n个账单，m个人，每次给出账单信息——k个人一共花了c元，每个要付 $\lceil\frac{c}{k}\rceil$ ，求每个人要付多少(1e5)

$\qquad$ 模拟即可

3,n个数，k次操作，每次操作是选两个数ai,aj，然后变成x,y，条件是ai * aj = x * y，求最后n个数和最大值

$\qquad$ 对n个数排序后，显然是尽量把大的数乘到an中去，模拟一下，最后求和即可

4，重排两个数组(长500，值域[-500,500])，使得每个位置符合ai + bi ∈[1,m]，m是给的

$\qquad$ 重排两个数组，等价于固定住一个数组，另一个变化。先对两个数组排序，然后固定住a，看b数组，对于a的每个位置i，b可以求出一个范围[l,r],使得任意j∈[l,r]满足ai + bj ∈[1,m]举个例子

m = 3

a:1,2,3

b:1,2,3

$\qquad$ 对于a中第一个位置a=1，b中1,2,3是满足的;a=2,b中1是满足，可以发现b中满足的数总是一个区间。

那对a中每个位置都求出b中一个合法区间，然后问题就转化成经典问题:n个区间限制，每个限制里只能取一个数，最后是否能全部取完

$\qquad$ 对于这个问题，贪心解决即可。我们对n区间按照r排序，再按照l排序，然后遍历每条限制，每次取最小的且满足大于等于l的位置i即可，有一次不能取到则判断为No（所以这题数据范围可以拉更大，500的话是有dp做法吗，暂时想不到，求大佬知道的话求留言捏）

讲的可能不是很明白，贴下代码

#define int long long 
using namespace std;
const int N = 5e2+10;
const int mod = 1e9+7;
int n,m,k;
int a[N],b[N];
array<int,2> line[N];
void solve(){
    set<int> st;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        st.insert(i);
    }
    for(int i=1;i<=n;i++){
        cin >> b[i];
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    int flag = 1;
    for(int i=1;i<=n;i++){
        if(a[i]+b[n] < 1)
            flag = 0;
        if(a[i]+b[1] > m)
            flag = 0;
        int p1 = lower_bound(b+1,b+1+n,1-a[i]) - b;
        int p2 = upper_bound(b+1,b+1+n,m-a[i]) - b - 1;
        if(flag==0)
            break;
        line[i] = {p1,p2};
    }
    sort(line+1,line+1+n,[&](auto A,auto B){
        return A[1] != B[1] ? A[1] < B[1] : A[0] < B[0];
    });
    for(int i=1;i<=n;i++){
       auto [l,r] = line[i];
       // cout << l << " " << r << endl;
       auto it = st.lower_bound(l);
       if(it==st.end() || it > r){
        flag = 0;
        break;
       }
       st.erase(it);
    }   
    cout << (flag?"Yes":"No") << endl;
}
signed main() {
    int T;cin>>T;
    while(T--){
        solve();
    }
}

5，求一个最长区间，满足区间平均数为k

$\qquad$ 二分写到一半，看了眼样例发现假了。。。写一下公式，然后脑子又清醒了

设 $pre_i$ 为前缀和i，我们要找的区间[l,r]要满足 $pre_r-pre_{l-1}=k(r-l＋1)$

拆一下有， $pre_r-kr=pre_{l-1}-k(l-1)$ ，那么我们枚举r，然后每次找下是否有满足这个条件的最小l即可。注意初始化0

牛客markdown怎么一堆显示bug，只能贴图片了

#define int long long 
using namespace std;
const int N = 2e5+10;
const int mod = 1e9+7;
int n,m,k;
int a[N],pre[N];
map<int,int> mp;
signed main() {
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];    
    }
    mp[0] = 0;
    int ans = -1;
    for(int i=1;i<=n;i++){
        if(mp.count(pre[i]-k*i)){
            ans = max(ans,i - mp[pre[i]-k*i]);
        }
        else {
            mp[pre[i]-k*i] = i;
        }
    }
    cout << ans;
}