CF1674E题解

ncwzdlsd · 2023-09-27 10:15:18 · 题解

分讨。

• op.1

最先非正的两个数为序列最小值和次小值。

直接找序列的最小值 \min_1 和次小值 \min_2，将 \min_1 和 \min_2 不断减 2。总花费为 \lceil\dfrac{\min_1}{2}\rceil+\lceil\dfrac{\min_2}{2}\rceil。

• op.2

最先非正的两个数为相邻的两个数。

若两个数中的一个不小于另一个数的两倍，那么可以通过不断地对较大数进行操作得到两个非正数。总花费为\lceil\dfrac{\max(a_i,a_{i+1})}{2}\rceil。

否则，以这两个数为整体，每次操作可以使两数之和减小 3，对两数进行轮流操作，

• op.3

最先非正的两个数为序列中距离为 2 的两个数。

无论如何，每次操作只能使这两个数和不断减小 1。总花费为 \lceil\dfrac{a_{i-1}+a_{i+1}}{2}\rceil。

这里也可以把两个数分开来看计算花费，但是显然没有整体法简洁。

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
int a[maxn],n,c1,c2,c3,b[maxn];

void op1()
{
    sort(b+1,b+n+1);
    c1=(b[1]+1)/2+(b[2]+1)/2;
}

void op2()
{
    c2=0x3f3f3f;
    for(int i=1;i<n;i++)
    {
        if(a[i+1]>=a[i]*2||a[i]>=a[i+1]*2) c2=min(c2,(max(a[i],a[i+1])+1)/2);
        else c2=min(c2,(a[i]+a[i+1]+2)/3);
    }
}

void op3()
{
    c3=0x3f3f3f;
    for(int i=2;i<n;i++) c3=min(c3,(a[i-1]+a[i+1]+1)/2);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    op1(),op2(),op3();
    cout<<min(c1,min(c2,c3));
    // cout<<c1<<endl<<c2<<endl<<c3;
    return 0;
}