stl专题

集训队

A - Moo University - Financial Aid POJ - 2010

有一个奶牛大学，给N个学生提供助学金，最多能提供F。现在有C个学生选择，给出了这些学生的成绩以及相应的助学金，然而学校希望这个N个学生的成绩的中位数尽可能地大，求这个中位数的最大值。
优先队列

#include<iostream>
#include<cstdio>
#include<queue>
#include <functional>
#include<map>
#include<limits>
#include<algorithm>
#define INF  0x3f3f3f3f
const int maxn = 100000+10;
using namespace std;
pair<int, int>cows[maxn];
priority_queue<int>q;
int n, c, ans = -1;
long long f;
int lcow[maxn], rcow[maxn];
int main()
{
    scanf("%d%d%lld", &n, &c, &f);
    for (int i = 0; i < c; i++)
        scanf("%d%d", &cows[i].first, &cows[i].second);
    int res = 0;
    sort(cows, cows + c);
    for (int i = 0; i < c; i++)
    {
        if (q.size() == (n - 1) / 2)
            lcow[i] = res;
        else
            lcow[i] = INF;
        res += cows[i].second;
        q.push(cows[i].second);
        if (q.size() >(n - 1) / 2)
        {
            res -= q.top();
            q.pop();
        }
    }
    while (!q.empty()) q.pop();
    res = 0;
    for (int i = c-1; i >=0; i--)
    {
        if (q.size() == (n - 1) / 2)
            rcow[i] = res;
        else
            rcow[i] = INF;
        res += cows[i].second;
        q.push(cows[i].second);
        if (q.size() > (n-1) / 2)
        {
            res -= q.top();
            q.pop();
        }
    }
    for (int i = c-1; i >=0; i--)
    {
        if (lcow[i] + rcow[i] + cows[i].second <= f)
        {
            ans = cows[i].first;
            break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

自补：
poj 2823

n个长度队列，k长度滑块每次从左向右滑动1长度，求这个序列中的最小值与最大值，并输出这个最小值和最大值分别构成的序列
解法：单调队列Or线段树，使用双端队列维护下标，这里若直接使用优先队列会tle

#include <iostream>
#include <cstdio>
#include <cstring>
const int maxn = 1e6+5;
using namespace std;
int b[maxn],a[maxn],c[maxn];
int deq[maxn];
int n,k;
void getmin()
{
    int s=0,t=0;
    for(int i=0;i<n;i++)
    {
        while(s<t&&a[deq[t-1]]>=a[i])   t--;
        deq[t++]=i;
        if(i-k+1>=0)
        {
            b[i-k+1]=a[deq[s]];
            if(deq[s]==i-k+1)
                s++;
        }
    }
    for(int i=0;i<=n-k;i++)
    {
        printf("%d%c",b[i],i==n-k?'\n':' ');
    }
}
void getmax()
{
    int s=0,t=0;
    for(int i=0;i<n;i++)
    {
        while(s<t&&a[deq[t-1]]<=a[i]) t--;
        deq[t++]=i;
        if(i-k+1>=0)
        {
            b[i-k+1]=a[deq[s]];
            if(deq[s]==i-k+1)
                s++;
        }
    }
    for(int i=0;i<=n-k;i++)
    {
        printf("%d%c",b[i],i==n-k?'\n':' ');
    }
}
int main()
{
    int s=0,t=0;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    getmin();
    memset(deq,0,sizeof(deq));
    getmax();
    return 0;
}