标签：std begin end ++ CF1928B ans size

赛时犯大病，维护区间实现的时候把满足条件的区间末尾直接设置成区间开头，还找不出hack数据

分析

通过读题，可以得出两个结论：

• \(a\)​ 数组中一组相同的数中只有一个能对答案造成贡献。

  • 因为排列中每个数不同，相同的数加不同的数不可能得出相同的数。

• 一段去重后的数列要贡献答案长度，当且仅当该数列的最大值与最小值之差小于等于 \(n - 1\)。

  • 因为一段数列内只要没有重复数字，同时最大值与最小值之差小于等于 \(n - 1\)，肯定能通过加上 \(1\sim n\)​ 的排列而相等。

实现

• 针对第一个性质，对数组排序后去重：

  std::sort(a.begin(), a.end());
  a.erase(std::unique(a.begin(), a.end()), a.end());
  

• 针对第二个性质：

  • 排序数组（去重时已做到）。

  • 在最多 $ O(n\log n)$ 的时间复杂度下维护一段最大值与最小值之差小于等于 \(n - 1\)​ 的序列。

    • 双指针维护

      for (int i = 0, j = 0; i < a.size(); i++) {
      	while(j < a.size() && a[i] + n - 1 >= a[j]) j++;//如果满足性质二，后方指针后移
      	ans = std::max<int>(ans, j - i);
      }
      

    • 二分查找

      for (int i = 0; i < a.size(); i++) {
      	i64 sum = std::upper_bound(a.begin(), a.end(), a[i] + n - 1) - a.begin() - i;//直接找以当前这个元素为最小值的符合性质二的最大的最大值的位置，再与当前位置做差求出序列长度
      	ans = std::max(ans, sum);
      }
      

代码

• 双指针实现

  void solve() {
      int n;
      std::cin >> n;
      std::vector<i64> a(n);
      for (auto& i : a) std::cin >> i;
      std::sort(a.begin(), a.end());
      a.erase(std::unique(a.begin(), a.end()), a.end());
      i64 ans = 0;
      for (int i = 0, j = 0; i < a.size(); i++) {
  		while(j < a.size() && a[i] + n - 1 >= a[j]) j++;
  		ans = std::max<int>(ans, j - i);
  	}
      std::cout << ans << '\n';
  }
  

• 二分查找实现

  void solve() {
      int n;
      std::cin >> n;
      std::vector<i64> a(n);
      for (auto& i : a) std::cin >> i;
      std::sort(a.begin(), a.end());
      a.erase(std::unique(a.begin(), a.end()), a.end());
      i64 ans = 0;
      for (int i = 0; i < a.size(); i++) {
          i64 sum = std::upper_bound(a.begin(), a.end(), a[i] + n - 1) - a.begin() - i;
          ans = std::max(ans, sum);
      }
      std::cout << ans << '\n';
  }
  

标签：std,begin,end,++,CF1928B,ans,size
From： https://www.cnblogs.com/kdlyh/p/18013702