D. Omkar and Circle
题意
n(奇数)个数排成一个⚪ 首尾相接
现在反复进行一种操作
取出一个数 然后它两侧的数相加成为新的数
最后只剩1个数
问这个数最大多少
题解
首先想到贪心的两种策略
1.尽量保留最大的
2.尽量让多个数相加留到最后
比如7个数
a b c d e f g
假设最后剩下的数为x
它最多由原先4个数相加最少由原先2个数相加
而这四个数是从⚪的某个位置切断形成链后间隔取到的
推广到n个数形成的⚪ 最少由(n-1)/2个数相加 最少由2个数相加
若想让x是n个数中y个数相加 {y<(n-1)/2}
那它一定是(n-1)/2个数相加的中的某种情况去掉一些数得到的
比如7个数
a b c d e f g
选择最终x由三个数相加得到
去掉b得到 a+c d e f g
去掉f得到 a+c d e+g
去掉e+g 得到 a+c+d
实际上它是 a+c+d+f 的和去掉f
a+c+d+f是去掉b，e，g得到的结果
所以得出结论贪心策略是留下尽量多的数相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
typedef pair<ll,ll> P;
const int mod=2e3;
const int Max=4e5+5;
ll data[Max];
int main(){
Turnoff;
int n;cin>>n;
ll ans=0,sum=0;
for(int i=0;i<n;i++){
cin>>data[i];
data[i+n]=data[i];
}
if(n==1){
cout<<data[0]<<endl;
return 0;
}
sum=0;ll temp=0;bool flag=0;
int L=0;
for(int i=0;i<2*n;i++){
sum+=data[i];
if((i&1)==flag){
temp+=data[i];
}
if(i-L+1>=n){
ans=max(ans,temp);
temp=sum-temp;
flag=!flag;
sum-=data[L];
L++;
}
}
cout<<ans<<endl;
return 0;
}
|