https://codeforces.com/contest/1435/submission/96757666 --> 使用 set.upper_bound() https://codeforces.com/contest/1435/submission/96761788 --> 使用 upper_bound(set.begin() , set.end())
我注意到 set.upper_bound() 比后者更快（后者给出了 Time Limit Exceeded）。这是为什么？
下面的代码给出了超过时间限制
int ind = *upper_bound(st.begin(), st.end(), mp[i], Greater< int >());
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
# define ld long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
typedef priority_queue<ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<ll> maxheap;
#define …的问题是从本文给出了拍摄中，我们必须找出是否有两个不同的指数i和阵列以J，使得绝对之间差NUMS [I]和NUMS [j]的是至多吨和我之间的绝对差j至多为k。我的方法是 O(N*N) 这不应该是可以接受的，但它是。
接受的代码：
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int n = nums.size();
vector<pair<long long, int>>list;
for (int i = 0; i < n; i++)
list.push_back(make_pair(nums[i], i));
sort(list.begin(), list.end());
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n && list[j].first-list[i].first <= t; j++)
if (abs(list[j].second - list[i].second) <= k)
return true;
}
return false; …