牛客多校(2020第九场)F Groundhog Looking Dowdy
输入
4 3 1 3 2 8 6 1 2 3 1 7 5
输出
2
说明
Apple will pay attention to Groundhog's clothes on day 1, 3, and 4 ,Groundhog will wear clothes with dowdiness of 3, 2, and 1 on day 1, 3, and 4,and the difference is 2.
备注:
题解：
题目大意：给出 n 天，每天可以有数件衣服可以选择，但每天只能选择一件衣服穿，每件衣服都有权值，现在需要挑出 m 天的衣服，使得最大值与最小值之差最小
思路：首先我们可以把它存入一个数组，并根据它们的权值排序，然后枚举左端点，使用尺取法确定右端点， 由于已经排序，那么答案维护一下右端点权值 - 左端点权值即可
尺取法的精髓在于在时间复杂度为O(n)的情况下，枚举出你所需要的东西，所以枚举的每一个点都需要坐处理，如果当初用不到便存储起来
1 #include<iostream> 2 #include<algorithm> 3 #include<set> 4 #include<vector> 5 #include<cstring> 6 #include<unordered_map> 7 #include<cstdio> 8 #include<queue> 9 using namespace std; 10 11 #define P pair<int, int> 12 const int N = 1e6 + 5; 13 14 vector <P> clo; 15 int cnt[N]; 16 17 bool cmp(P a, P b) { 18 return a.second < b.second; 19 } 20 21 int main() { 22 int n, m; 23 scanf("%d %d", &n, &m); 24 25 for (int i = 1; i <= n; i++) { 26 int k; 27 scanf("%d", &k); 28 while(k--) { 29 int val; 30 scanf("%d", &val); 31 clo.emplace_back(i, val); //pair输入 32 } 33 } 34 sort(clo.begin(), clo.end(), cmp); 35 36 //尺取 37 int r = 0, now = 0, ans = 0x3f3f3f3f;//now用来统计不同的天数有几个 38 memset(cnt, 0, sizeof(cnt)); //记录遍历过的每天的衣服的数量 39 for (int l = 0; l < clo.size(); l++) { 40 while (now < m && r < clo.size()) { 41 if (cnt[clo[r].first] == 0) { 42 now++; //如果这一天的衣服第一次出现，天数加1 43 } 44 cnt[clo[r].first]++; 45 r++; 46 } 47 48 if (now == m) { 49 ans = min(ans, clo[r-1].second - clo[l].second); 50 } 51 cnt[clo[l].first]--; 52 if (cnt[clo[l].first] == 0) { 53 now--; 54 } 55 } 56 57 printf("%d\n", ans); 58 }