堆排序

堆排序首先要建堆，自下而上的建堆．构成一个大顶堆，使得一个节点大于他的两个儿子．

然后只要根据取最大，然后把他拎出去就可以得到一个从小到大的排列了．

#include<cstdio>
void maxHeap(int *a,int n,int i)
{
    //left、right、largest分别指向
    //左孩子、右孩子、{a[i],a[left]}中最大的一个
    int left,right,largest;
    largest=left=2*i;
    if(left>n)
        return;
    right=2*i+1;
    if(right<=n && a[right]>a[left]){
        largest=right;
    }
    if(a[i]<a[largest]){//根结点的值不是最大时,交换a[i]，a[largest]
        a[i]=a[i]+a[largest];
        a[largest]=a[i]-a[largest];
        a[i]=a[i]-a[largest];
        //自上而下调整堆
        maxHeap(a,n,largest);
    }
}

//建堆
void creatHeap(int *a,int n)
{
    int i;
    //自下而上调整堆
    for(i=n/2;i>=1;i--)
        maxHeap(a,n,i);
}

//堆排序
void heapSort(int *a,int n)
{
    int i;
    creatHeap(a,n);//建堆
    for(i=n;i>=2;i--){
        //堆顶记录和最后一个记录交换
        a[1]=a[1]+a[i];
        a[i]=a[1]-a[i];
        a[1]=a[1]-a[i];
        //堆中记录个数减少一个，筛选法调整堆
        maxHeap(a,i-1,1);
    }
}
int main()
{
    int i;
    int a[7]={0, 5,1,7,9,8,2};//不考虑a[0]
    heapSort(a,6);
    for(i=1;i<=6;i++)
        printf("%-4d",a[i]);
    printf("\n");
}

常见的堆操作

void push_heap(int *a,int x, int n)//在大小为n的堆尾部(也就是一维数组的n+1的位置) 添加 x  
{  
    a[++n] = x; //添加  
    int i = n;  
    while(i > 1 && a[i/2] < x)//我们一层一层的往上比较，插入，对于一个大根堆，如果上面的数小，就要把小的数下降  
    {  
        a[i] = a[i/2];  
        i /= 2;  
    }  
    a[i] = x;//最后的插入  
}
//删除最大的．
void pop_heap(int *a, int n)   
{  
    int x = a[1];  
    a[1] = a[n];  
    n--;  
    heap(a,n,1);  
    return x;  
}

各种堆的复杂度

项目	二叉堆	左偏树	二项堆	Fibonacci堆
构建	O(N)	O(N)	O(N)	O(N)
插入	O(log N)	O(log N)	O(log N)	O(1)
取最小节点	O(1)	O(1)	O(log N)	O(1)
删除最小节点	O(log N)	O(log N)	O(log N)	O(log N)
删除任意点	O(log N)	O(log N)	O(log N)	O(log N)
合并	O(N)	O(log N)	O(log N)	O(1)
空间需求	最小	较小	一般	较大
编程复杂度	最低	较低	较高	十分大

习题

POJ - 2010

带限制的01背包．这里是要保证价值的中位数最大

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
const int maxn = 1e5+30;
const int inf = 0x3f3f3f3f;
using namespace std;
int n,c,f;
int half;
pair<int, int>cow[maxn];
int lower[maxn], upper[maxn];

void init(int st, int ed, int *a){
    int total = 0;
    priority_queue<int>q;
    bool flag = st<ed;
    if(flag){
        for(int i = st; i < ed; i++){
            a[i] = (q.size() == half? total:inf);
            q.push(cow[i].second);
            total += cow[i].second;
            if(q.size() > half){
                total -= q.top(); q.pop();
            }
        }
    } else {
        for(int i = st; i >= ed; i--){
            a[i] = (q.size() == half? total:inf);
            q.push(cow[i].second);
            total += cow[i].second;
            if(q.size() > half){
                total -= q.top(); q.pop();
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(~scanf("%d%d%d",&n,&c,&f)) {
        half = n/2;
        for(int i = 0; i < c; i++) {
            scanf("%d%d",&cow[i].first, &cow[i].second);
            /*
            if(cow[i].second > f) {
                i --;
                c --;
            }
            */
        }
        sort(cow, cow+c);
        //预处理
        init(0, c, lower);
        init(c-1, 0, upper);
        //
        int ans = -1;
        for(int i = c-1; i >= 0; i--) {
            if(lower[i] + cow[i].second + upper[i] <= f) {
                ans = cow[i].first;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

没有理解二分的含义就是会这样的．要保证一个区间内都能满足．

错误代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
const int maxn = 1e5+30;
using namespace std;

int n,c,f;
int ans;
struct cow{
    int score, aid, rak;
    cow() {}
    cow(int score, int aid): score(score), aid(aid){}
}cows[maxn],cowa[maxn];

inline bool cmp_score(cow a, cow b){
    if(a.score == b.score)return a.aid < b.aid;
    return a.score < b.score;
}

inline bool cmp_aid(cow a, cow b){
    if(a.aid == b.aid)return a.score < b.score;
    return a.aid < b.aid;
}

int main () {
    ios::sync_with_stdio(false);cout.tie(0);
    while(~scanf("%d%d%d",&n,&c,&f)){
        for(int i = 0; i < c; i++){
            scanf("%d%d",&cows[i].score, &cows[i].aid);
            if(cows[i].aid > f)
                i--,c--;
        }
        sort(cows, cows+c, cmp_score);
        for(int i = 0; i < c; i++){
            cows[i].rak = i;
        }
        memcpy(cowa, cows, sizeof cows);
        sort(cowa, cowa+c, cmp_aid);
        int l = 0, r = c, mid;
        ans = -1;
        //二分中间值
        while(r>l+1){
            mid = (l+r)>>1;
            int left = 0, right = 0, total = cows[mid].aid;
            //贪心的选取
            for(int i = 0; i < c ; i++){
                if((cowa[i].rak < mid) && (total + cowa[i].aid <= f) && (left < n/2)){
                    total += cowa[i].aid;
                    left++;
                }else if((cowa[i].rak > mid) && (total + cowa[i].aid <= f) && (right < n/2)){
                    total += cowa[i].aid;
                    right++;
                }
            }
            if((left < n/2) && (right < n/2)){
                ans = -1;break;
            }else if(left < n/2){
                l = mid;
            }else if(right < n/2){
                r = mid;
            }else {
                ans = cows[mid].score;
                l = mid;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C - Fence Repair POJ - 3253

状态压缩，每一层可能数都继承了上一层．

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[13][1<<13];
int n,m,a[15];
int mod = 100000000;
bool judge(int x, int y){
    if((a[x]&y)!=y)return 0;
    if((y&(y<<1))) return 0;
    return 1;
}

void work(){
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    //计算i层每种状态量的个数．一直往下加．i和i-1层都枚举２两边的1<<m，做了一些特判优化．
    //因为i只与上一层有关，如果空间不够可以考虑滚动数组．
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < (1<<m); j++){
            if(!judge(i, j))continue;
            for(int k = 0; k < (1<<m);k++){
                if((j&k)!=0)continue;
                dp[i][j] += dp[i-1][k];
                dp[i][j]%=mod;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < (1<<m); i++){
        ans += dp[n][i];
        ans %= mod;
    }
    printf("%d\n",ans);
}

int main(){
     while(~scanf("%d%d",&n,&m)){
        //每行转化为二进制
        for(int i = 1; i <= n; i++){
            a[i] = 0;
            for(int j = 1; j <= m; j++){
                int k;
                scanf("%d",&k);
                a[i] = (a[i] << 1)+k;
            }
        }
        work();
     }
    return 0;
}

E - Monkey KingHDU - 1512 ** (左偏树＋并查集)

并查集判断是否认识，左偏树用来合并堆．

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 1e5+30;
int n;
struct node{
    int key, dis;
    int lson, rson;
    int fa;
}ltree[maxn];

void build(int x, int k){
    ltree[x].key = k;
    ltree[x].fa = x;
    ltree[x].lson = ltree[x].rson = 0;
    ltree[x].dis = (x==0)?-1:0;
}

int fid(int x){
    if(ltree[x].fa == x)return x;
    else return fid(ltree[x].fa);
}

int mer(int x, int y){
    if(x == 0)return y;
    if(y == 0)return x;
    //swap
    if(ltree[x].key < ltree[y].key)swap(x,y);
    ltree[x].rson = mer(ltree[x].rson, y);
    //swap 子树
    int &l = ltree[x].lson, &r = ltree[x].rson;
    ltree[l].fa = ltree[r].fa = x;
    if(ltree[l].dis < ltree[r].dis)
        swap(l ,r);
    if(r == 0)ltree[x].dis = 0;
    else ltree[x].dis = ltree[r].dis + 1;
    return x;//返回键值(较大的)
}

int del(int rt){
    int l = ltree[rt].lson;
    int r = ltree[rt].rson;
    ltree[l].fa = l;
    ltree[r].fa = r;
    ltree[rt].dis = ltree[rt].lson = ltree[rt].rson = 0;
    return mer(l, r);
}

int slove(int x, int y){
    ltree[x].key >>= 1;
    ltree[y].key >>= 1;
    int left,right;
    left = mer(del(x), x);
    right = mer(del(y), y);
    left = mer(left, right);
    return ltree[left].key;
}

void init(){
    for(int i = 1; i <= n; i++){
        int strong;
        scanf("%d",&strong);
        build(i, strong);
    }
    build(0, 0);
}

void output(){
    int q,x,y,fx,fy;scanf("%d",&q);
    for(int i = 0; i < q; i++){
        scanf("%d%d",&x,&y);
        fx = fid(x), fy = fid(y);
        if(fx == fy)puts("-1");
        else printf("%d\n",slove(fx, fy));
    }
}

int main(){
    while(~scanf("%d",&n)){
        init();
        output();
    }
}

poj 3666

离散化，好像调整后的数字都是原数字中出现．

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
const int maxn = 2e3+5;
using namespace std;

int a[maxn],b[maxn];
ll dp[maxn][maxn];
int n;
// dp[i][j] 代表的是i位数字j代表最后一位是b[j];
void slove(){
    for(int i = 1; i <= n; i++){
        ll minn = dp[i-1][1];
        for(int j = 1; j <= n; j++){
            minn = min(minn, dp[i-1][j]);
            dp[i][j] = abs(a[i]-b[j])+minn;
        }
    }
    ll ans = dp[n][1];
    for(int i = 1; i <= n; i++){
        ans = min(ans, dp[n][i]);
    }
    printf("%lld\n",ans);
}

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",a+i);
        b[i] = a[i];
    }
    sort(b+1, b+n+1);
    slove();
}