[C++知识库] C. Unequal Array

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> C. Unequal Array -> 正文阅读

[C++知识库]C. Unequal Array

https://codeforces.com/contest/1672/problem/C
在这里插入图片描述
input

4
5
1 1 1 1 1
5
2 1 1 1 2
6
1 1 2 3 3 4
6
1 2 1 4 5 4

output

在这里插入图片描述
题意
给定长度为 $n$ 的序列 $a$ 中，通过 $0$ 次或多次以下操作使得序列中只出现 $0$ 次或 $1$ 次相邻两个数相等的情况

选定两个相邻的点位并将其同时赋值为 $x$ ，形式上为：选定 $i$ （小于n），使得 $a_i = a_{i+1} = x$ ， $x$ 为任意取值

思路
我们发现，如果我们使用了一次操作，则选择的两个位置上就会变成相同的，即会贡献 $1$ 对相等

我们尝试一些例子，如下图：

{ $1, 1, 1$ }
则直接修改一次即可
{ $1, 1, 1, 1$ }
则也是修改一次

可以手动模拟一下 { $1, 1, 1, 1, 1$ }，则需要两次
会发现除了{ $1, 1, 1$ }比较特殊，其余都是 $r ? l ? 1$ 的次数

综上对于连续出现的可以这样子修改

但是对于不连续出现的，因为每次操作都会留下 $1$ 对相等，则我们并不能分开处理每一批连续出现的数

所以实际上我们相当于通过操作将每片连在一起，即从最左边第一次出现相邻相等的数，一直链接到最右边相邻相等的数

如以下：
{ $1, 1, 2, 1, 1$ }
{ $1, 1, 2, 3, 1, 1$ }
在这里插入图片描述

在这里插入图片描述
最后会发现答案的计算都为： $r ? l ? 1$ ，最后记得对长度为3就特判一下，不然公式会计算为0

AC代码
$c n t$ 为统计出现相邻相等的对数
$l 、 r$ 记录最左端和最右端

#include <bits/stdc++.h>
#define endl '\n'
#define AC return 0;
using namespace std;
//#define ll long long
//#define int long long

int a[200005];
void slove()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int l = n,r = 1;
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(a[i] == a[i - 1])
        {
            l = min(l,i - 1);
            r = max(r,i);
            cnt++;
        }
    }
    if(cnt < 2)
        cout << 0 << endl;
    else
    {
        int k = r - l - 1;
        if(k == 1)
            cout << 1 << endl;
        else
            cout << k - 1 << endl;
    }   
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin >> T; while(T--)
    slove();
    AC
}