优先队列练习 优先队列/贪心

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

目录

一.常规优先队列

1001

[NOIP2004]合并果子

1008

Cut

 二.贪心/优先队列维护

1003

第k小 维护优先队列*

1004

tokitsukaze and Soldier*

1005

[JSOI2007]建筑抢修 贪心**

一.常规优先队列

1001	[NOIP2004]合并果子

比较基本的优先队列，因为是随机合并，很容易想到每次都合并最小的两堆，所以使用优先队列， 每次从队列中取出两个最小的堆，合并为一堆后push两堆和起来的一堆进队列，重复。

#include
using namespace std;

#define f first
#define s second
#define ll long long
#define int ll
#pragma warning (disable:4996);
const int N = 2e5 + 10;
int T, n, m, k;
int a, b, c;
int pre[N];
int w[N];
int sum;

priority_queue,greater>q;//小根堆

void bfs() {
    while (q.size()>1) {
        int t1 = q.top();
        q.pop();
        int t2 = q.top();
        q.pop();
        q.push(t1 + t2);
        sum += (t1 + t2);
    }
}
signed main()
{
    ios::sync_with_stdio(false); cout.tie(NULL);
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // !ONLINE_JUDGE
    cin >> n;
    for (int j = 1; j <= n; j++) {
        cin >> w[j];
        q.push(w[j]);
    }
    bfs();
    cout << sum;
}

1008

Cut

直接看好像是固定顺序不能使用优先队列，但其实反过来看，其实就是给定一些随机的数，合并成一个序列。因为是随机分割的连续序列。所以跟上一题类似，每次合并两个最大的，如何推入大根堆里。

#include

using namespace std;
#pragma GCC optimize(2)
#define f first
#define s second
#define ll long long
#define int ll
#pragma warning (disable:4996);
const int N = 2e5 + 10;
int T, n, m, k;
int a, b, c;
signed main()
{
     ios::sync_with_stdio(false); cout.tie(NULL);
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // !ONLINE_JUDGE
    cin >> n;
    priority_queueq;
    for (int j = 1; j <= n; j++) {
        int t;
        cin >> t;
        q.push(t);
    }
    int ans = 0;
    while (q.size() >= 2) {
        int t1, t2;
        t1 = q.top();
        q.pop();
        t2 = q.top();
        q.pop();
        q.push(t1 + t2);
        ans += t1 + t2;
    }
    cout << ans << endl;
}

 二.贪心/优先队列维护

有些数据量过大的题不能直接优先队列模拟，可以考虑去根据数据动态调整维护一个固定用途的优先队列，达到O(1)的处理，根据数据调整优先度也就涉及到了贪心策略的选择，有些难题很难想到正确的贪心，还是要多练习练习。

1003	第k小 维护优先队列*

 

 求第k小本来是能用快排的分治思想解决的，但这题的询问次数过多，分治的复杂度O（n）都很难过，所以去学习了优先队列的做法，先贴一下分治的做法

inline int fnd(int l, int r, int p) {

    if (l == r && l == p) return v[p];
    if (l < r) {
        int i = l, j = r;
        int tmp = v[l];
        while (i < j) {
            while (i < j && v[j] >= tmp) --j;
            if (i < j) swap(v[i], v[j]);
            while (i < j && v[i] <= tmp) ++i;
            if (i < j) swap(v[i], v[j]);
        }
        v[i] = tmp;
        if (i == p) return v[p];
        if (i > p) return fnd(l, i - 1, p);
        else return fnd(i + 1, r, p);
    }
    return 0;
}

然后是优先队列的做法，推入所有元素然后pop肯定是行不通的，要再优化复杂度的话就要动态处理，因为我们其实只需要当前序列中最小的k个元素，第k小的元素就在size为k的小根堆的队首。所以我们想到去维护一个size为k的小根堆，保证这k个元素是序列中最小的七个。如果添加一个新元素，这个元素比队列中最大的元素都大，那也没必要加入队列中，如果比队列中最大的元素小，那么我们就可以把当前队列中最大的元素pop掉，保证队列中的元素是整个序列中最小的k个。

基于这个思路，我们可以先排序取出初始的k个最小的元素，然后根据添加元素动态调整队列，询问时队列中的最大值（队首）也就是第k小的元素

然后就是当维护的队列中元素不足k个，则加一个push一个，最后也没到k输出-1.

#include
#pragma warning (disable:4996);
#define ll long long 
#define int ll
#define mem(a,b) memset(a,b,sizeof(a))
 
using namespace std;
const int N = 2e5 + 10;
int n,m, k, q, T;
int a, b, c;
int arr[N];
signed main() {
    ios::sync_with_stdio(false); cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("out.txt", "w", stdout);
#endif
    cin >> n >> m >> k;
    for (int j = 1; j <= n; j++)
        cin >> arr[j];
    priority_queueq;
    sort(arr + 1, arr + 1 + n);
    for (int j = 1; j <= n; j++){
        if (j > k)break;
        q.push(arr[j]);
    }
    for (int j = 1; j <= m; j++) {
        int t1, t2;
        cin >> t1;
        if (t1 == 1) {
            cin >> t2;
            q.push(t2);
            if (q.size() > k)
                q.pop();
        }
        else {
            if (q.size() < k)cout << -1 << endl;
            else cout << q.top() << endl;
        }
    }
}

---

1004	tokitsukaze and Soldier*

 

 初见很像动态规划，虽然不知道能不能做..

本题的思路跟上一题相似还是维护一个优先队列，但是此时的限制条件更加复杂，是在不断变动的。所以可以考虑枚举限制条件。

枚举限制条件s[i],先思考一下如何枚举，如果是从小到大，或者直接枚举。那我们超过s[i]被pop的元素再下一次枚举到了更大的s[i]是没有办法再push回来的。所以想到去从大到小枚举s[i]，这样先前因为大于s[i]被pop的元素也会被下一个限制s的时候pop，也就不会产生矛盾。

确定枚举的顺序后，就是处理每一个限制条件下，该如何维护优先队列。首先，在人数限制固定的情况下我们要得到当前情况最大的战力，在人数没满的时候直接push就行，只会增大战力。但是当人数达到了当前的限制，那么保证同等人数下总战力最大，那么新push的战力至少要比队列中最小的战力要大。所以大致思路就出来了。

从大到小枚举人员限制s，期间维护一个size为s[i]的元素为战力值的小根堆，当队列的人数大于人员限制的时候不断从小pop出超过s[i]的人，最后得到的就是当前人员限制下的最高战力。然后对所有情况的战力取最值即可

#include

using namespace std;
#define ll long long
#define int ll
#pragma warning (disable:4996);
const int N = 2e5 + 10;
int T, n, m, k;
struct node {
    int v, s;
    int operator<(const node& a)const {
        return s > a.s;//按大到小排序
    }
}p[N];
int v[N], s[N];
signed main()
{
    ios::sync_with_stdio(false); cout.tie(NULL);
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // !ONLINE_JUDGE
    priority_queue, greater>q;//v小的优先
    cin >> n;
    for (int j = 1; j <= n; j++) {
        cin >> p[j].v >> p[j].s;
    }
    sort(p + 1, p + 1 + n);
    int sum = 0;
    int ans = INT_MIN;
    for (int j = 1; j <= n; j++) {
        node now = p[j];
       
        while (q.size() >= now.s) {//留出一个位置给当前限制的人
            sum -= q.top();
            q.pop();
        }
        q.push(now.v);
        sum += now.v;
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

1005	[JSOI2007]建筑抢修 贪心**

 这题的难点就是不知道如何贪心，但是有一个地方非常明确，就是快倒的房子修补的优先权更高，但是又涉及到时间消耗，快倒的房子如果时间消耗过大影响了后面房子的修补也不划算，所以这题的贪心也要考虑时间消耗，同等条件下，时间消耗小的房子修补了肯定比消耗大的房子修补后更容易到达最优解。

但是我们可以回溯到当时消耗较大的房子处选择不修他，转而修同等条件下时间消耗更小的房子。

大致思路就能出来了，先按快倒的房子修补，直到当前修补的时间超过当前房子的最晚时间（t2-t1）就开始比较这个修补这个房子的价值和之前修补过的房子的价值谁更高，很明显是时间消耗更小的更有利于修补更多的房子，所以pop出之前修补过的最大的房子，加入现在的房子

#include
#pragma warning (disable:4996);
#define ll long long 
#define int ll
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 2e5 + 10;
int n,m, k, q, T;
int a, b, c;
int arr[N];
struct node {
	int t1, t2;
	int operator<(const node& a)const {
		return t2 < a.t2;
	}
}p[N];
signed main() {
	std::ios::sync_with_stdio(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("out.txt", "w", stdout);
#endif
	cin >> n;
	for (int j = 1; j <= n; j++) {
		cin >> p[j].t1 >> p[j].t2;
	}
	int nowTime = 0;
	int ans = 0;
	priority_queueq;//维护时间消耗队列
	sort(p + 1, p + n + 1);//从结束时间小到大，因为快倒的房子先修要紧
	for (int j = 1; j <= n; j++) {
		node now = p[j];
		if (nowTime <= now.t2 - now.t1) {
			nowTime += now.t1;
			q.push(now.t1);
			ans++;
		}
		else {
			if (q.top() > now.t1) {//如果这个房子修补了比之前消耗大的房子合算，那么放弃原来的//房子转而修补当前这个。
				nowTime +=(now.t1-q.top());//返回去不修之前代价大的，而是修现在这个
				q.push(now.t1);
				q.pop();
			}
		}
	}
	cout <