<分区>
[挑战结束]
问题:
正元素数组。 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 直到结束 来自对中索引的原始数组。
- 重复第 3 步和第 4 步 每 x.
- 打印原始数组。
我认为我的解决方案的复杂度为 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;
}