双指针

From Bistre Pheasant, 3 Years ago, written in Plain Text, viewed 303 times.
URL http://axuhongbo.top/paste/view/7044a4f6 Embed
Download Paste or View Raw
  1. /**
  2.  * CTU Open 2017
  3.  * Problem Solution: Ice cream samples
  4.  * Idea: Use two pointers to consecutively enlarge/shorten result interval - linear time solution
  5.  * @author Josef Malik
  6.  */
  7.  
  8. #include <algorithm>
  9. #include <cmath>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <iostream>
  14. #include <sstream>
  15. #include <map>
  16. #include <set>
  17. #include <queue>
  18. #include <vector>
  19.  
  20. using namespace std;
  21.  
  22. typedef long long int ll;
  23. typedef pair<int, int> pii;
  24.  
  25. #define PB push_back
  26. #define MP make_pair
  27.  
  28. #define FOR(prom, a, b) for(int prom = (a); prom < ((int)(b)); prom++)
  29. #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
  30. #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
  31. #define R1(a) do{scanf("%d", &(a));}while(0)
  32. #define R2(a, b) do{scanf("%d%d", &(a), &(b));}while(0)
  33. #define R3(a, b, c) do{scanf("%d%d%d", &(a), &(b), &(c));}while(0)
  34. #define SV(vec) do{int s_v_;scanf("%d", &(s_v_));vec.PB(s_v_);}while(0)
  35. #define MM(co, cim) memset((co), (cim), sizeof((co)))
  36. #define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
  37. #define INF 1000000007
  38.  
  39. int n, k, li, p1, p2, ct[1000014], ctu, ctc, res;
  40. vector<int> st[1000014];
  41.  
  42. int main ()
  43. {
  44.   while (scanf("%d%d", &n, &k) != -1)
  45.   {
  46.     FOR(i, 0, n) st[i].clear();
  47.     FOR(i, 0, n)
  48.     {
  49.       R1(li);
  50.       FOR(j, 0, li) SV(st[i]);
  51.     }
  52.     res = INF;
  53.     MM(ct, 0);
  54.     p1 = ctc = ctu = 0;
  55.     p2 = -1;
  56.     while (p1 < 2 * n)
  57.     {
  58.       if (p2 == 2 * n - 1 || p2 - p1 + 1 >= n || ctu == k)
  59.       {
  60.         if (ctu == k) res = min(res, ctc);
  61.         FOR(i, 0, st[p1 % n].size())
  62.         {
  63.           if (--ct[st[p1 % n][i]]);else --ctu;
  64.           --ctc;
  65.         }
  66.         ++p1;
  67.       }
  68.       else
  69.       {
  70.         ++p2;
  71.         FOR(i, 0, st[p2 % n].size())
  72.         {
  73.           if (++ct[st[p2 % n][i]] == 1) ++ctu;
  74.           ++ctc;
  75.         }
  76.       }
  77.     }
  78.     printf("%d\n", res == INF ? -1 : res);
  79.   }
  80.    
  81.   return 0;
  82. }

Reply to "双指针"

Here you can reply to the paste above

captcha