【チャレンジ終了】
問題：
正の要素の配列。Deepu 配列の要素を減らしたい。彼は、X より大きい配列内のすべての要素を 1 だけ減らす関数 Hit(X) を呼び出します。
彼はこの配列を何度も呼び出します。Hit(X) を何度も呼び出した後、配列を出力します。
入力：
n----- 配列 10^5 の要素の数。
n 個の要素 ----- 1<=要素<=10^9。
x----- Hit(X) x 要素への呼び出しの数----- 1<=要素<=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;
}