灵茶 – 2023 – 12 – 12

链接

Problem - 620C - Codeforces

思路 : 

贪心 : 对于每一段区间,从前往后贪,如果前面一段区间有重复数字,那么就直接合并成答案的一段区间,然后继续寻找下一段区间,对于最后一段,如果没有匹配的话,就直接合并到已经加入到答案的最后一段区间里面;

代码 : 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl 'n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
#define PII pair<int,int>
typedef long long LL;
const int mod = 1e9+7;
const int N = 3e5+10;
using namespace std;

int n ;
int a[N];

inline void solve(){
	cin >> n;
	vector<PII> b;
	int ans = 0;
	unordered_map<int,int> mp;
	int pre = 1;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<=n;i++){
		mp[a[i]]++;
		if(mp[a[i]]>1){
			ans ++;
			mp.clear();
			b.push_back({pre,i});
			pre = i + 1;
		}
	}
	int x,y;
	if(!b.size()) cout << -1 << endl;
	else{
		cout << ans << endl;
		int len = b.size();
		for(int i=0;i<len-1;i++) cout << b[i].first << " " << b[i].second << endl;
		cout << b[len-1].first << " " << n << endl;
	}
	return ;
}
 
signed main()
{
    IOS
    int _ = 1;
    // cin >> _;
    while(_ --) solve();
    return 0;
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>