B. Light It Up-白红宇

B. Light It Up

阅读量：2125 次

发布时间：2019-04-30

本文共 1422 字，大约阅读时间需要 4 分钟。

题意

有一盏灯，在0开启，在M关闭，开始有N个时刻，相邻时刻分别表示开启或者关闭。问怎么插入一个时刻使得灯亮的总时间最大，输出最大值。

AC

暴力的枚举每个区间，计算插入得到的值

因为插入一个时刻的话，会打乱之前的顺序，所以先对原来的时刻进行预处理，求sum1和sum2

sum1正常区间的和， sum2是后移一位的区间和

当插入一个时刻，分为两种情况，插入到奇数后，插入到偶数个之后

插入到奇数之后：
x - r + sum1[ l ] + sum2[ n ] - sum2[ r ]

插入到偶数之后：
r - x + sum1[ l ] + sum2[ n ] - sum2[ r ]

更新最大值即可

#include 
   
    #include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define N 100005#define mem(a, b) memset(a, b, sizeof(a))#define P pair
           
            #define pb push_backusing namespace std;int a[N];int sum1[N], sum2[N];int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int n, m; while (~scanf("%d%d", &n, &m)) { // 将 0 和 M 插入数组 a[1] = 0; n++; for (int i = 2; i <= n; ++i) { scanf("%d", &a[i]); } n++; a[n] = m; // 计算sum1 for (int i = 2; i <= n; i += 2) { sum1[i] = sum1[i - 2] + a[i] - a[i - 1]; sum1[i + 1] = sum1[i]; } // 计算sum2 for (int i = 3; i <= n; i += 2) { sum2[i] = sum2[i - 2] + a[i] - a[i - 1]; sum2[i + 1] = sum2[i]; } // 不插入的ans int ans = sum1[n]; // 枚举区间，更新ans for (int i = 1; i < n; ++i) { if (i % 2) { int t = a[i + 1] - a[i] - 1 + sum1[i] + sum2[n] - sum2[i + 1]; ans = ans > t ? ans : t; }else { int t = a[i + 1] - a[i] - 1 + sum1[i] + sum2[n] -sum2[i + 1]; ans = ans > t ? ans : t; } } printf("%d\n", ans); }#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}