当前位置:   article > 正文

Codeforces Round #700 (Div. 2) D1 D2. Painting the Array 思维

Codeforces Round #700 (Div. 2) D1 D2. Painting the Array 思维

link

题意: 给一个数组,让你从头开始选出一些数放在 A A A数组中,剩下的放在 B B B数组中,且是有序选择,让后把两个数组中相邻且相等的元素合并。
D1: 使合并后 L e n ( A ) + L e n ( B ) Len(A)+Len(B) Len(A)+Len(B)最大。
D2: 使合并后 L e n ( A ) + L e n ( B ) Len(A)+Len(B) Len(A)+Len(B)最小。

为了方便,先假设 A B 结尾选择的数组下标分别为 p1 p2 。 n e x t [ i ] next[i] next[i]表示下标为 i i i对应的值的下一个位置, n o w now now为当前遍历到的数组下标。
先考虑D1:
因为要求最小,我们可以贪心的来往后面填数,我们分成如下情况:
(1) a [ n o w ] = = a [ p 1 ] a[now]==a[p1] a[now]==a[p1] 那么填在p2处更好
(2) a [ n o w ] = = a [ p 2 ] a[now]==a[p2] a[now]==a[p2] 那么填在p1处更好
(3) n e x t [ p 1 ] < n e x t [ p 2 ] next[p1]<next[p2] next[p1]<next[p2] 那么填在p1更好,这个也比较值观,比如当前数组 A A A中最后的 a [ p 1 ] = 7 a[p1]=7 a[p1]=7,数组 B B B中最后的 a [ p 2 ] = 6 a[p2]=6 a[p2]=6,而还没有填的数依次为 a [ n o w ] = 8 , a [ n o w + 1 ] = 6 , a [ n o w + 2 ] = 6 a[now]=8,a[now+1]=6,a[now+2]=6 a[now]=8,a[now+1]=6,a[now+2]=6,这个时候 n o w now now填在哪个合适呢?显然是填在 B B B数组合适,因为我们要尽量让相同的数不合并,如果填在了 A A A,那么会使得相同的合并。
对于D2
跟D1差不多,只需要改动一点,依旧分成以下几种情况:
(1) a [ n o w ] = = a [ p 1 ] a[now]==a[p1] a[now]==a[p1] 那么填在p1处更好
(2) a [ n o w ] = = a [ p 2 ] a[now]==a[p2] a[now]==a[p2] 那么填在p2处更好
(3) n e x t [ p 1 ] < n e x t [ p 2 ] next[p1]<next[p2] next[p1]<next[p2] 那么填在p2更好,因为填在p2可以尽可能的让即将到来的 n e x t [ p 1 ] next[p1] next[p1] p 1 p1 p1合并。

D1:

//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n;
int a[N],pos[N],ne[N];

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);

    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<=n;i++) pos[i]=n+1;
    for(int i=n;i>=0;i--)
    {
        ne[i]=pos[a[i]];
        pos[a[i]]=i;
    }
    int ans=0,p1=0,p2=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==a[p1]) { ans+=a[i]!=a[p2]; p2=i; }
        else if(a[i]==a[p2]) { ans+=a[i]!=a[p1]; p1=i; }
        else if(ne[p1]<ne[p2]) { ans+=1; p1=i; }
        else { ans+=1; p2=i; }
    }
    printf("%d\n",ans);




















	return 0;
}
/*

*/



  • 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
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

D2:

//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n;
int a[N],pos[N],ne[N];

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);

    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<=n;i++) pos[i]=n+1;
    for(int i=n;i>=0;i--)
    {
        ne[i]=pos[a[i]];
        pos[a[i]]=i;
    }
    int ans=0,p1=0,p2=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==a[p1]) p1=i;
        else if(a[i]==a[p2]) p2=i;
        else if(ne[p1]>ne[p2]) { ans+=1; p1=i; }
        else { ans+=1; p2=i; }
    }
    printf("%d\n",ans);




















	return 0;
}
/*

*/









  • 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
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/71313
推荐阅读
相关标签
  

闽ICP备14008679号