【挑战结束】
问题：
一组正元素。Deepu 想减少数组的元素。他调用了一个函数 Hit(X)，它将数组中大于 X 的所有元素减少 1。
他会多次调用这个数组。在多次调用 Hit(X) 后打印数组。
输入：
n----- 数组 10^5 中没有元素。
n 个元素 ----- 1<=元素<=10^9。
x----- 对 Hit(X) x 个元素的调用次数----- 1<=element<=10^9。
输出：
打印调用 Hit(X) x 次后的数组。
时间限制--5 秒。
我的解决方案给出了 Time Limit Exceeded。
我的做法：
- 保留原始数组
- 创建数组元素对的向量及其在数组中的索引 对向量元素进行排序 [ 升序 ]。
- 执行 C++ STL 的 LowerBound() 以获取元素在向量中的位置，其中元素等于给定元素 x。
- 从这个元素开始，将大于 x 的元素减少 1，直到从对中的索引开始在原始数组中结束。
- 对每个 x 重复步骤 3 和 4。
- 打印原始数组。
我认为我的解决方案复杂度为 n^2。
谁能给我一个优化的解决方案
谢谢
#define _CRT_DISABLE_PERFCRIT_LOCKS
// lower_bound/upper_bound example
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vector
#include <utility>
using namespace std;
bool pairCompare(const std::pair<long long int, unsigned int>& firstElem, const std::pair<long long int, unsigned int>& secondElem) {
return firstElem.first < secondElem.first;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
unsigned int n, m;
long long int arr[100000], x,temp;
vector<pair<long long int, unsigned int> > vect(100000);
cin >> n;
for (unsigned int i = 0; i < n; i++)
{
cin >> temp;
arr[i] = temp;
vect[i].first = temp;
vect[i].second = i;
}
sort(vect.begin(), vect.begin() + n, pairCompare);
cin >> m;
vector<pair<long long int, unsigned int> >::iterator low;
while (m--)
{
cin >> x;
low = lower_bound(vect.begin(), vect.begin() + n, make_pair(x,2), pairCompare);
if (low != vect.begin() + n)
{
for (unsigned int i = low - vect.begin(); i < n; i++)
{
if (vect[i].first != x)
{
vect[i].first -= 1;
arr[vect[i].second] -= 1;
}
}
}
}
for (unsigned int i = 0; i < n; i++)
{
cout << arr[i]<<" ";
}
return 0;
}