D. Matryoshkas

题目链接????????????????

题目大意

给你一个序列，然后对序列进行拆分，要求分出来的集合，满足集合内各个元素连续且不重复，问最少可以分为多少个集合

思路

首先我们先统计出相同元素的个数，然后根据元素值从小到大进行遍历，将这些连续离散的点，理解成一个函数图像，我们只要统计出极大值点的个数(包括边界的最大值)，那么这个最大值就是这个连续段分配的出集合的最小个数

但是这样处理后，后面的极大值点元素的个数值，不能直接加上，因为这个连续的区间共享最底下的元素

所以后面的要减去共享的部分，这样处理起来就比较麻烦了，所以我们直接统计连续段相邻元素的个数的差值，这样既统计了极大值的值，又消除了连续区间，后续极大值的共享个数相减的问题

代码

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std; 
int main(){

    int t;
    std::cin>>t;
    while(t--){ 
    ll n,tmp;
    std::cin>>n;
    std::map<ll , ll> mp;

    for(int i=0;i<n;i++){
        std::cin>>tmp;
        mp[tmp]++;
    }
    pair<ll ,ll>pre;
    bool tag = true;
    int cnt = 0;
    for(auto x:mp){
        if(tag){
            pre.fi=x.fi;
            pre.se=x.se;
            tag=false;
            cnt = x.se;
        }  
        else {
        if(x.fi==pre.fi+1)cnt+=max(0ll,x.se-pre.se);
        else cnt+=x.se;
        }
        pre.fi= x.fi;
        pre.se= x.se;
    }


    std::cout<<cnt<<'n'; 
    
    }
                                
    return 0;
}      

最后

以上就是发嗲雪碧为你收集整理的D. MatryoshkasD. Matryoshkas的全部内容，希望文章能够帮你解决D. MatryoshkasD. Matryoshkas所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。