2023NOIP A层联测28

联测28"/>

2023NOIP A层联测28

现在有 n n n 只青鸹，每只青鸹有一个毒瘤系数，他们排成了一个序列。

你可以重复以下操作，直到序列中只剩下一只青鸹的时候停止，每次操作可以自选进行 1 1 1 还是 2 2 2 操作，并且自选进行操作的位置：

1. 选择一只在序列端点位置的青鸹，将这只青鸹杀死。

2. 选择一只在序列非端点位置的青鸹（假设在 i i i 位置），将这只青鸹（ i i i 位置）杀死，将这只青鸹旁边的两只青鸹（ i − 1 i-1 i−1 与 i + 1 i+1 i+1 位置）合体（即合体为一只青鸹，其毒瘤系数为两只青鸹的毒瘤系数加起来的和），放在 i i i 位置上。

每次操作结束后，如果一个位置没有青鸹，则其后面的青鸹会自动补位，也就是说不会有空位。

你想让最后剩下的青鸹的毒瘤系数最高，请输出这个最高的毒瘤系数，并且输出最少操作次数。

n ≤ 1 0 6 n\le10^6 n≤106

显然两个数要对答案产生贡献，二者之间的数的个数必为奇数，如果是偶数，就不能仅删除中间的部分。

手模后发现，设对答案产生贡献的数为 a p 1 , a p 2 , … , a p k a_{p_1},a_{p_2},\dots,a_{p_k} ap1​​,ap2​​,…,apk​​， p 1 ≡ p 2 ≡ ⋯ ≡ p n ( m o d 2 ) p_1\equiv p_2\equiv\dots\equiv p_n\pmod 2 p1​≡p2​≡⋯≡pn​(mod2)。

所以最优策略是在奇数或偶数位置选全部正数，然后确定了选的数后，把相邻两个数之间的连续段删去即可，发现中间的最小操作次数就是连续段长度除以 2 2 2，两边的段单独求。

特判序列全部都是负数的情况。

时间复杂度 O ( n ) O(n) O(n)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dis(x) (x>1?(x+1>>1):0)
constexpr ll INF=1e18;
const int N=1e6+1;
int n,cnt1,cnt2;
ll ans1,ans2,a[N];
struct node
{ll x,i;
}b1[N],b2[N];
int main()
{freopen("friends.in","r",stdin);freopen("friends.out","w",stdout);cin.tie(0)->sync_with_stdio(0);int fl=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(i&1) b1[++cnt1]={a[i],i};else b2[++cnt2]={a[i],i};if(a[i]>0) fl=1;}if(!fl){ll maxn=-INF,maxi;for(int i=1;i<=n;i++){if(maxn<a[i]){maxn=a[i];maxi=dis(i)+dis(n-i+1);}else if(maxn==a[i]) maxi=min(maxi,1ll*dis(i)+dis(n-i+1));}cout<<maxn<<"\n"<<maxi;return 0;}ll maxi=-INF,mini=INF,sum=0;for(int i=cnt1;i>=1;i--){if(b1[i].x<=0) continue;sum+=b1[i].x;maxi=max(maxi,b1[i].i);mini=min(mini,b1[i].i);}ans1=sum,ans2=(maxi-mini)/2+dis(mini)+dis(n-maxi+1);sum=0,maxi=-INF,mini=INF;for(int i=cnt2;i>=1;i--){if(b2[i].x<=0) continue;sum+=b2[i].x;maxi=max(maxi,b2[i].i);mini=min(mini,b2[i].i);}if(ans1<sum) ans1=sum,ans2=(maxi-mini)/2+dis(mini)+dis(n-maxi+1);else if(ans1==sum) ans2=min(ans2,(maxi-mini)/2ll+dis(mini)+dis(n-maxi+1));cout<<ans1<<"\n"<<ans2;
}