codeforces1353D 优先队列

1353D

D题解题思路就是利用优先队列模拟过程即可

只要每次把某一段的起点和终点压入队列，根据段长来排序，一直到处理完所有的点为止

这里先扩展一下优先队列相关的用法

定义：priority_queue<Type, Container, Functional>

Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式。

//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

这个题就需要自己重写比较方法，和重写sort的cmp差不多

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <stdio.h>
#include <cmath>
#include <string.h>
#include <deque>

using namespace std;
#define ll long long
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;
static const int INF=0x3f3f3f3f;
int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll Pow(ll a,ll b,ll mod){if(b==0) return 1%mod; ll sum=1; a=a%mod; while(b>0) { if(b%2==1) sum=(sum*a)%mod; b/=2; a=(a*a)%mod;}return sum;}

typedef pair<int,int> pos;
struct cmp
{
    bool operator()(const pos p1,const pos p2)
    {
        if(p1.second-p1.first==p2.second-p2.first)
        return p1.first>p2.first;
        return p1.second-p1.first<p2.second-p2.first;
    }
};
priority_queue<pos,vector<pos>,cmp> que;
int v[200005];
int main()
{
    freopen("C:\Users\16599\Desktop\in.txt","r",stdin);
    int _;
    cin>>_;
    while (_--)
    {
        memset(v,0,sizeof(v));
        int n;
        cin>>n;
        int k=1;
        que.push(make_pair(1,n));
        while(!que.empty())
        {
            pair<int,int> p=que.top();
            que.pop();
            int l=p.first;
            int r=p.second;
            int mid=(l+r)/2;
            v[mid]=k++;
            if(mid-1>=l)
            que.push(make_pair(l,mid-1));
            if(mid+1<=r)
            que.push(make_pair(mid+1,r));
        }
        for(int i=1;i<=n;i++)
        cout<<v[i]<<" ";
        cout<<endl;
    }
    
    return 0;
}