第一行:N
第2至N+1行:每行1个数
第一行:最小的区间长度 区间个数X (以空格进行分隔)
第二行:X个区间的起始和结束位置,按照出现的顺序有序输出,多个区间之间以空格分隔,每个区间的输出格式如下所示:[start,end],最后以换行结尾
10 1 1 3 4 6 6 5 1 3 3
6 3 [2,7] [3,8] [4,9]
#include <bits/stdc++.h> using namespace std; struct P{ int l, r; }; int main(){ set<int> S; unordered_map<int, int> mp; vector<P> r; int n, cnt=0, Min=INT_MAX; scanf("%d", &n); int a[n]; for(int i=0;i<n;i++){ scanf("%d", &a[i]); S.insert(a[i]); } int i=0; for(int j=0;j<n;j++){ if(mp[a[j]] == 0) cnt++; mp[a[j]]++; while(cnt >= S.size()){ if(mp[a[i]] == 1) cnt--; mp[a[i]]--; if(j-i+1 < Min){ r.clear(); Min = j-i+1; r.push_back({i, j}); }else if(j-i+1 == Min) r.push_back({i, j}); i++; } } printf("%d %d\n", Min, (int)r.size()); for(int i=0;i<r.size();i++) printf("[%d,%d] ", r[i].l+1, r[i].r+1); return 0; }
#include<bits/stdc++.h> using namespace std; int main(){ #ifdef ONLINE_JUDGE #else freopen("E:/input.txt", "r", stdin); #endif unordered_map<int,int> mp; unordered_map<int,int> _mp; int n; scanf("%d",&n); vector<int>num; num.push_back(0); for(int i = 0; i < n; ++i) { int tmp; scanf("%d",&tmp); num.push_back(tmp); _mp[tmp] = 1; } int m = _mp.size(); int cnt = 0; int ans = n+1; vector<pair<int,int> > res; for(int i = 1,j = 1; j <= num.size(); ++j) { if(!mp[num[j]]) ++cnt; mp[num[j]]++; if(cnt == m) { while(mp[num[i]] > 1) { mp[num[i]]--; i++; } if(j - i + 1 < ans) { ans = j - i + 1; res.clear(); res.push_back(pair<int,int>(i,j)); }else if(j - i + 1 == ans) { res.push_back(pair<int,int>(i,j)); } } } printf("%d %d\n",ans,res.size()); for(int i = 0; i < res.size(); ++i) { printf("[%d,%d]",res[i].first,res[i].second); if(i < res.size()-1) printf(" "); else { printf("\n"); } } return 0; }感谢评论区,用map会超时,用unordered_map就过了
#include <bits/stdc++.h> #define MAX_N 5000005 using namespace std; int first[10000], second[10000]; int data[MAX_N]; int main(){ int n; scanf("%d", &n); set<int> key; for(int i = 0; i < n; i++){ scanf("%d", &data[i]); key.insert(data[i]); } int num = key.size(); //求解 int i = 0, j = 0; int count = 0; unordered_map<int, int> appear; while(i <= j && j <= n){ //找齐了数字 if(appear.size() == num){ //第一次出现全部数字,或者出现的数字的区间等于最小的区间 if(count == 0 ||second[count - 1] - first[count - 1] == j - i - 1){ //区间编号从1到N first[count] = i + 1; second[count++] = j; } //有更小的区间出现,重新赋值区间 else if(second[count - 1] - first[count - 1] > j - i -1){ count = 0; first[count] = i + 1; second[count++] = j; } //进行下一步的搜索,i向前移动,并在已经出现的map中减去 if(appear[data[i]] == 1) appear.erase(data[i]); else appear[data[i]] --; i ++; } //没有找齐,继续插入数字 else appear[data[j++]] ++; } printf("%d %d\n", second[0] - first[0] + 1, count); for(int i = 0; i < count; i ++) printf("[%d,%d]%c", first[i], second[i], i == count-1 ? '\n': ' '); return 0; }
#include <iostream> #include <set> #include <vector> #include <unordered_map> using namespace std; int main(){ int n; scanf("%d", &n); vector<int> array(n,0); set<int> s; for(int i=0;i<n;i++){ scanf("%d", &array[i]); s.insert(array[i]); } int left = 0, right = 0; vector<vector<int>> res; unordered_map<int, int> tmp; int min_len = n; while (right < n) { if (tmp.find(array[right]) == tmp.end()) tmp[array[right]] = 1; else { tmp[array[right]]++; } if (tmp.size() == s.size()) { break; } right++; } while (right < n) { while ( right - left +1 >= s.size() && tmp.size() == s.size()) { if (right - left + 1 <= min_len) { vector<int> t(2, 0); t[0] = left; t[1] = right; res.push_back(t); min_len = right - left + 1; } tmp[array[left]] --; if (tmp[array[left]] == 0) { tmp.erase(array[left]); } left++; } right++; if (tmp.find(array[right]) == tmp.end()) { tmp[array[right]] = 1; } else tmp[array[right]] ++; } int count = 0; for (int i = 0; i < res.size(); i++) { //cout << res[i][0] +1 << "--" << res[i][1] + 1<< endl; if (res[i][1] - res[i][0] + 1 == min_len) { count++; } } printf("%d %d\n", min_len, count); for (int i = 0; i < res.size(); i++) { if (res[i][1] - res[i][0] + 1 == min_len) { printf("[%d,%d] ", res[i][0] + 1, res[i][1] + 1 ); } } printf("\n"); return 0; }
#include <cstdio> #include <iostream> #include <vector> #include <climits> #include <unordered_set> #include <unordered_map> using namespace std; int main() { int n; scanf ("%d", &n); vector<int> A(n); unordered_set<int> Set; unordered_map<int, int> winHash; for (int i = 0; i < n; ++i) { scanf("%d", &A[i]); Set.insert(A[i]); } vector<pair<int, int>> ans; int count = Set.size(), winnum = 0; int left = 0, right; int minlen = INT_MAX; for (right = 0; right < n; ++right) { if (winHash[A[right]]++ == 0) winnum++; while (left <= right && winnum == count) { if (right-left+1 < minlen) { minlen = right-left+1; ans.clear(); } if (right-left+1 == minlen) ans.push_back({left+1, right+1}); if (--winHash[A[left]] == 0) winnum--; left++; } } int nans = ans.size(); printf("%d %d\n", minlen, nans); for (int i = 0; i < nans; ++i) { printf(" [%d,%d]"+!i, ans[i].first, ans[i].second); } printf("\n"); return 0; }
滑动窗口思想 开始用cin超时 用scanf就没有这回事了。搞不懂搞不懂。 #include<iostream> (720)#include<set> #include<vector> (721)#include<unordered_map> #include<stdio.h> using namespace std; int main(void){ int N; cin>>N; set<int> s; int num; int MinLen = 5000000; unordered_map<int, int> windows; vector<int> v; vector<vector<int>> ans; int n = 0; for (int i = 0; i < N; i++){ scanf("%d", &num); s.insert(num); v.push_back(num); } int i = 0; for (int j = 0; j < N; j++){ if (windows[v[j]] == 0) n++; windows[v[j]]++; while (n >= s.size()){ if (windows[v[i]] == 1){ n--; } windows[v[i]]--; if (j - i + 1 < MinLen){ ans.clear(); MinLen = j - i + 1; ans.push_back(vector<int> {i, j}); } else if(j - i + 1 == MinLen){ ans.push_back(vector<int> {i, j}); } i++; } } cout<<MinLen<<" "<<ans.size()<<endl; for (int i = 0; i < ans.size(); i++){ cout<<"["<<ans[i][0]+1<<","<<ans[i][1]+1<<"]"<<" "; } cout<<endl; return 0; }
N = int(input()) from collections import defaultdict d = set() res = [] for i in range(N): temp = int(input()) res.append(temp) if temp not in d: d.add(temp) total = [] min_length = len(res) temp = defaultdict(int) start,end = 0,1 temp[res[0]] = 1 temp_len = 1 while(end<N+1): if temp_len==len(d): if end-start<min_length: total=[[start+1, end]] min_length = end-start elif end-start==min_length: total.append([start+1, end]) if temp[res[start]]==1: temp_len-=1 temp[res[start]]-=1 start+=1 else: if end <N and temp[res[end]]==0: temp_len+=1 if end<N: temp[res[end]]+=1 end+=1 print(min_length,len(total)) for i in total: print('['+str(i[0])+','+str(i[1])+']', end=' ') print(end='\n')