08.26美团笔试AK

比19号那场简单了不少，19号只做了两题QAQ

第一题：

当是3的倍数时，浇水施肥，否则只浇水

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x, y, z;
    cin >> x >> y >> z;
    int ans = 0;
    int cnt = 0;
    while(ans < z)
    {
        if(cnt % 3 == 0)
            ans += (x + y);
        else
            ans += x;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

第二题：

用map存一下每个人的消费

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    int k, c, x;
    map<int, ll>mp;
    while(n--)
    {
        cin >> k >> c;
        ll tmp = 1LL * ceil(1.0 * c / k);
        for(int i = 0; i < k - 1; i++)
        {
            cin >> x;
            mp[x] += tmp;
        }
    }
    for(int i = 1; i <= m; i++)
        cout << mp[i] << ' ';
    return 0;
}

第三题：

每次取出最大值和次大值，然后将最大值和次大值的乘积放回，同时放一个1进去。用大根堆来维护。

不知道为什么用C++的priority_queue卡80%了，改用Python实现了。

import heapq

que = []
n, k = map(int, input().split())
s = input().split()
for i in s:
    heapq.heappush(que, int(-int(i)))
while k > 0:
    biggest = heapq.heappop(que)
    bigger = heapq.heappop(que)
    bigger *= -1
    biggest *= -1
    heapq.heappush(que, -1)
    heapq.heappush(que, -1 * bigger * biggest)
    k -= 1
ans = 0
while que:
    ans += heapq.heappop(que)
print(-1 * ans % int(1e9 + 7))

第四题：

一个数组升序排序，另一个降序排序，判断排序后两数组对应位置的和是否在区间里。如果所有的位置的和都在该区间里，输出Yes，否则输出No

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int q;
    cin >> q;
    while(q--)
    {
        int n , m;
        cin >> n >> m;
        vector<int>a(n), b(n);
        for(int i = 0; i < n; i++)
            cin >> a[i];
        for(int i = 0; i < n; i++)
            cin >> b[i];
        sort(a.begin(), a.end());
        sort(b.begin(), b.end(), greater());
        int flag = 0;
        for(int i = 0; i < n; i++)
        {
            if(a[i] + b[i] > m || a[i] + b[i] < 1)
            {
                flag = 1;
                break;
            }
        }
        if(flag)
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    return 0;
}

第五题：

子数组平均值为k，可以转换成子数组和为0的问题。用map统计和为sum出现的最早的位置，当和再次为sum时，即两个sum之间的这段子数组的和为0。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() 
{
    int n, k;
    ll x;
    cin >> n >> k;
    ll sum = 0;
    map<ll, int>mp;
    int ans = -1;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        ll tmp = 1LL * k - x;
        sum = sum + tmp;
        if(sum == 0)
            ans = max(ans, i + 1);
        if(mp.count(sum) > 0)
        {
            ans = max(ans, i - mp[sum]);
        }
        else
            mp[sum] = i;
    }
    cout << ans << endl;
    return 0;
}