CodeForces 1000B Light It Up（贪心、思维）

https://codeforces.com/problemset/problem/1000/B

题意：

一个模拟思维题。就是有一盏灯，0时刻开着。n次操作，你可以在其中加入一次操作（或者不加），操作为：a[i]时刻按一下开关，状态变为相反状态（开->关or关->开）。问灯亮着的时长最长为多少？

样例一0~4开（时长为4-0），4~6关（时长为6-4），6~7开（时长为7-6），7~10关（时长为10-7），可以这这些时间点中加操作使开灯时间变长 在3处加操作，开灯时长变为0～3（开）3～4（关）4～6（开）6～7（关）7～10（开）

给定n个数，和上界m，即在0到m个区间内插入n个数，形成n+1个区间，区间长度提取出来单独成一个序列。

可以选择其中至多一个数分裂，（x=y+z），求分裂后的奇数序和（tim[1]+tim[3]+....）问最大化是多少。

注意在拆分是，n如果要拆，肯定是拆成了1和n-1(n本身为1可以略过)，n-1为开灯时间

思路：

预处理加贪心

代码如下：

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <math.h>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 //const double PI=acos(-1);

 #define Bug cout<<"---------------------"<<endl

 const int maxn=1e5+;

 using namespace std;

 int A[maxn];//原数组

 int p[maxn];//差分数组求差值

 int sum[];//辅助数组

 int bhd_sum[maxn];//从后往前到i处的奇偶项之和

 int fot_sum[maxn];//从前往后到i处的奇偶项之和

 int main()

 {

     int n,m;

     scanf("%d %d",&n,&m);

     A[] = ;

     int flag = ;

     for(int i = ;i <= n;i++)

     {

         scanf("%d",&A[i]);

         p[i] = A[i] - A[i-];

         fot_sum[i] = fot_sum[i-] + flag*p[i];

         flag = !flag;

     }

     A[n+] = m;

     p[n+] = A[n+]-A[n];

     fot_sum[n+] = fot_sum[n] + flag*p[n];

     int cnt = ;

     for(int i = n+;i > ;i--)

     {

         sum[cnt%] += p[i];

         bhd_sum[i] = sum[cnt%];

         cnt++;

     }

     int ans = bhd_sum[];

     for(int i = ;i <= n+;i++)

     {

         ans = max(ans,fot_sum[i]- + bhd_sum[i+]);

     }

     printf("%d\n",ans);

 }

别人写的代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 #define ll long long

 #define N 1000005

 int n,m,a[N],l[N],ans=;

 int main()

 {

     cin>>n>>m;

     bool flag=; //开关

     l[]=;a[]=;

     for(int i=;i<=n;i++)

     {

         cin>>a[i];

         l[i]=l[i-]+flag*(a[i]-a[i-]);

         flag=!flag;  //感觉超级巧妙

     }

     l[n+]=l[n]+flag*(m-a[n]);//不加操作时的总时长

     ans=l[n+];

     for(int i=;i<=n;i++)

     {

         ans=max(ans,l[i]+m-a[i]-(l[n+]-l[i])-);  //相通之后太巧妙了啊！！

         /*m-a[i]是在这个点改变之后所有时长

         l[n+1]-l[i] 原来总开灯时长-这点之前开灯时长=这点之后开灯时长。而改变这个点后。后面所有开灯时长变成了关灯时长

         m-a[i]-(l[n+1]-l[i])也就是这个点   这个点改变之后所有时长- 关灯时长 =开灯时长

         还要-1，因为 都是在点的临近点操作*/

     }

     cout<<ans<<endl;

 }