如何在不改变运行结果的前提下优化时间复杂度:#include bitsstdc++husing namespace std;int main freopencardinrstdin; freopencardoutwstdout; long long n; cin n; vectorlong long pilen; for long long i = 0; i n; i+
要优化时间复杂度,可以考虑以下几点:
- 
避免使用不必要的数据结构和操作。在这段代码中,可以将能量卡片堆栈改为最小堆,这样可以避免每次插入都进行排序操作。
 - 
避免不必要的操作。在这段代码中,每次判断能量卡片是否为空都使用了
!energy_cards.empty(),可以在每次出栈后用一个bool变量记录能量卡片是否为空,避免重复判断。 - 
减少不必要的循环次数。在这段代码中,使用了两个循环遍历能量卡片堆栈和原始堆栈,可以将两个循环合并为一个循环,在遍历原始堆栈的同时进行能量卡片的处理。
 
优化后的代码如下:
#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    long long n;
    cin >> n;
    vector<long long> pile(n);
    for (long long i = 0; i < n; i++) {
        cin >> pile[i];
    }
    priority_queue<long long, vector<long long>, greater<long long>> energy_cards;
    long long total_energy = 0;
    bool energy_cards_empty = true;
    for (long long i = 0; i < n; i++) {
        if (pile[i] == 0) {
            if (!energy_cards_empty) {
                long long energy = energy_cards.top();
                energy_cards.pop();
                total_energy += energy;
                if (energy_cards.empty()) {
                    energy_cards_empty = true;
                }
            }
        } else {
            energy_cards.push(pile[i]);
            energy_cards_empty = false;
        }
    }
    cout << total_energy << endl;
    return 0;
}
优化后的代码将能量卡片堆栈改为最小堆,并且使用一个bool变量energy_cards_empty记录能量卡片是否为空,避免重复判断。同时,将两个循环合并为一个循环,在遍历原始堆栈的同时进行能量卡片的处理。这样可以减少不必要的数据结构和操作,提高代码的效率
原文地址: https://www.cveoy.top/t/topic/iGKI 著作权归作者所有。请勿转载和采集!