Codeforces Round #763 (Div. 2)C

这个D实在是不会，只能先补了C

C

C

这个题是我们可以选择从3到n

我们可以选择一个d(d>=0&&d<=ai/3),可以把2d给ai-2,那么ai-2+=2d,把d给ai-1,ai-1+=d,我们要找到实现n-2个操作后这些ai中的最小值的最大

对于最小值的最大化这一类问题，我们可以尝试用二分的方式来求解

对于这一题的check

我们可以通过判断x的情况是否符合条件

对于每一个d,我们可以通过贪心来求

ai的最大的一个d为ai/3，最小的为变化了的bi(加上它前面的对它的影响后的值)还需要预留出x，因为我们要保证最小的那一个数一定是x,所以我们需要从后往前遍历

我们最后来判断，如果存在一个数比此时我们给出的最小值x还要小，那么这一个就不符合条件了，return false

#include <iostream>
#include <vector>
using namespace std;
const int maxn=2e5+10;
#define int long long 
int n,t,k;
vector<int>a;
bool check(int x)
{
    vector<int>b=a;
    for (int i=n;i>=3;i--)
    {
        int d=min(a[i]/3,(b[i]-x)/3);
        b[i-2]+=2*d;
        b[i-1]+=d;
    }
    for (int i=1;i<=n;i++)
    {
        if (b[i]<x) return false;
    }
    return true;
}
void solve()
{
    cin>>n;
    a=vector<int>(n+1,0);
    int l=0,r=1e9+10;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        l=min(l,a[i]);
    }
    int mid,ans;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if (check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans<<'\n';
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}