#include <bits/stdc++.h> #define int long long using namespace std; using LL = long long; constexpr int mod = 1e9 + 7; constexpr int INF = 1e18 + 7; constexpr int N = 1e6 + 10; vector<int> zz_word_hint; int n, m, k; int a[N]; int f[N]; signed main() { cin >> n >> m; vector<int> b(n); for (int i = 1; i <= n; i++) { cin >> a[i]; b[i - 1] = a[i]; } sort(b.begin(), b.end()); k = n / 2; multiset<int, greater<int>> down(b.begin(), b.begin() + k); multiset<int> up(b.begin() + k, b.end()); while (m--) { int p, x; cin >> p >> x; if (a[p] > *down.begin()) { up.erase(up.find(a[p])); up.insert(x); a[p] = x; } else { down.erase(down.find(a[p])); down.insert(x); a[p] = x; } if (*down.begin() > *up.begin()) { int x1 = *down.begin(); int x2 = *up.begin(); up.erase(up.begin()); down.erase(down.begin()); up.insert(x1); down.insert(x2); } cout << *up.begin() << "\n"; } return 0; } 这个代码用到了什么算法?
时间: 2024-04-19 20:27:09 浏览: 9
这段代码使用了贪心算法和堆(multiset)数据结构。
在代码中,首先对数组a进行排序,然后将数组b划分为两个部分,分别存储了较大的一半数值和较小的一半数值。这里的划分依赖于n的值,即数组长度的一半。
然后,通过对down和up两个multiset进行操作,实现了每次替换数组中的元素,并保持down中的元素都小于等于up中的元素。具体操作是,如果要替换的元素大于down中的最大值,则在up中替换,并将该元素插入到down中;反之,如果要替换的元素小于等于down中的最大值,则在down中替换,并将该元素插入到up中。
在每次操作后,输出up中的最小值。
因此,这个代码使用了贪心策略来保持down和up两个集合的有序性,并使用multiset数据结构来维护集合的有序性和元素的插入和删除操作。
相关问题
#include <bits/stdc++.h> using namespace std
这段代码是一个C++的头文件引用和命名空间的使用示例。具体来说,`#include <bits/stdc++.h>`是一个常用的头文件引用方式,它包含了C++标准库中的所有头文件。而`using namespace std`则是为了使用`std`命名空间中的标准库函数和对象,这样就可以直接使用`cout`、`cin`等标准输入输出流对象,而不需要写`std::cout`、`std::cin`。
这种写法虽然方便,但也存在一些问题。首先,包含了所有的标准库头文件可能会导致编译时间变长。其次,使用了`using namespace std`会将整个`std`命名空间中的所有标识符引入当前作用域,可能会导致命名冲突。因此,在实际开发中,建议根据需要只包含需要的头文件,并使用具体的命名空间来避免潜在的问题。
#include <bits/stdc++.h> using namespace std;
这个头文件是C++11标准引入的,它包含了所有标准库中的头文件。使用这个头文件可以方便地在一个地方包含所有需要的头文件,而不需要一个一个地包含。这个头文件通常只在竞赛中使用,因为它不是标准C++头文件,不保证在所有编译器中都能正常工作。
以下是一个使用这个头文件的示例,实现输入4个整数a、b、c、d,将它们倒序输出:
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a << endl;
return 0;
}
```