Skip to content

11041: 【原1041】二哥打飞机

题目

题目描述

author: yydcool 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1041

Description

每当二哥45度仰望天空，他总是发现天上飞了许多飞机。

“实在是太不爽了，看我把这些飞机全部打下来！”--二哥

已知天上一共有N架飞机，从1...N编号，每架飞机有一个飞行高度。

二哥会跟你说decrease i j，表示第i架飞机的高度下降了j。

同时二哥还会一边问你findmin x，让你告诉他在高度大于x（不含等于）的飞机中哪一架飞机高度最低（如果相同，输出编号最小的）。

通常情况下x很小，以致于经常99%的飞机高度大于x。

高度有可能小于0哦。

N<=100000,二哥开口次数<=10000

Input Format

见样例

Output Format

见样例

Hint

用堆做吧

Sample Input

5
1 2 3 4 5
findmin 4
decrease 5 1
findmin 3
decrease 5 10
findmin 3
findmin -100

Sample Output

5
4
4
5

FineArtz's solution 

/* 二哥打飞机 */
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

class cmp{
public:
    bool operator()(pair<int, int> p1, pair<int, int> p2){
        return (p1.second < p2.second || (p1.second == p2.second && p1.first < p2.first));
    }
};

class Plane{
public:
    bool operator <(const Plane &p){
        return (h < p.h || (h == p.h && ind < p.ind));
    }

    int h = 0, ind = 0;
};

int n;
Plane a[100005];
int pos[100005];

void siftup(int x){
    while (x > 1){
        if (a[x] < a[x / 2]){
            a[0] = a[x / 2];
            a[x / 2] = a[x];
            a[x] = a[0];
            pos[a[x].ind] = x;
            pos[a[x / 2].ind] = x / 2;
            x /= 2;
        }
        else
            break;
    }
}

void makeheap(){
    for (int i = n / 2 + 1; i <= n; ++i)
        siftup(i);
}

int dfs(int x, int i){
    if (a[i].h > x)
        return i;
    int r1 = 0, r2 = 0;
    if (i * 2 <= n){
        r1 = dfs(x, i * 2);
    }
    if (i * 2 + 1 <= n){
        r2 = dfs(x, i * 2 + 1);
    }
    if (r1 == 0)
        return r2;
    else if (r2 == 0)
        return r1;
    else
        return (a[r1] < a[r2] ? r1 : r2);
}

void findmin(int x){
    int r = dfs(x, 1);
    cout << a[r].ind << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    set<pair<int, int>, cmp> s;
    cin >> n;
if (n <= 70000){
    for (int i = 1; i <= n; ++i){
        int h;
        cin >> h;
        s.insert(make_pair(i, h));
    }
    char ss[10];
    while (cin >> ss){
        if (ss[0] == 'd'){
            int x, d;
            cin >> x >> d;
            auto it = find_if(s.begin(), s.end(), [x](pair<int, int> p){return p.first == x;});
            auto t = *it;
            t.second -= d;
            s.erase(it);
            s.insert(t);
        }
        else if (ss[0] == 'f'){
            int x;
            cin >> x;
            auto it = find_if(s.begin(), s.end(), [x](pair<int, int> p){return p.second > x;});
            cout << it->first << '\n';
        }
    }
}
else{
    for (int i = 1; i <= n; ++i){
        cin >> a[i].h;
        a[i].ind = i;
        pos[i] = i;
    }
    makeheap();
    char s[10];
    while (cin >> s){
        if (s[0] == 'd'){
            int x, d;
            cin >> x >> d;
            a[pos[x]].h -= d;
            siftup(pos[x]);
        }
        else if (s[0] == 'f'){
            int x;
            cin >> x;
            findmin(x);
        }
    }
}
    return 0;
}

ligongzzz's solution 

#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    map<int, set<int>> mdata;
    vector<int> vdata(n + 1);

    for (int i = 1; i <= n; ++i) {
        int temp;
        cin >> temp;

        if (mdata.find(temp) == mdata.end()) {
            set<int> stmp;
            stmp.insert(i);
            mdata.insert(make_pair(temp, stmp));
        }
        else {
            mdata[temp].insert(i);
        }
        vdata[i] = temp;
    }

    string op;
    while (cin >> op) {
        if (op == "findmin") {
            int val;
            cin >> val;

            auto p = mdata.upper_bound(val);
            cout << *(p->second.begin()) << "\n";
        }
        else if (op == "decrease") {
            int i, j;
            cin >> i >> j;
            mdata[vdata[i]].erase(i);
            vdata[i] -= j;
            mdata[vdata[i]].insert(i);
        }
    }

    return 0;
}

WashSwang's solution 

#include <iostream>
#include <cstring>
using namespace std;
struct node{
    int n,h;
};
char cmd[200];
node heap[200000];
int ptr[200000],num,x,d;
inline int ls(int x){ return x<<1;}
inline int rs(int x){ return x<<1|1;}
void minheapify(int x){
    int s=x;
    while (true){
        if (ls(x)<=num&&(heap[ls(x)].h<heap[s].h||(heap[ls(x)].h==heap[s].h&&heap[ls(x)].n<heap[s].n))) s=ls(x);
        if (rs(x)<=num&&(heap[rs(x)].h<heap[s].h||(heap[rs(x)].h==heap[s].h&&heap[rs(x)].n<heap[s].n))) s=rs(x);
        if (s!=x)
        {
            swap(ptr[heap[s].n],ptr[heap[x].n]);
            swap(heap[s],heap[x]);
            x=s;
        }
        else break;
    }
}
void modify(int x,int d){
    heap[ptr[x]].h-=d;
    minheapify(ptr[x]);
    int cur=ptr[x];
    while (cur>1){
        if (heap[cur].h<heap[cur/2].h||(heap[cur].h==heap[cur/2].h&&heap[cur].n<heap[cur/2].n)){
            swap(ptr[heap[cur].n],ptr[heap[cur/2].n]);
            swap(heap[cur],heap[cur/2]);
            cur/=2;
        }
        else break;
    }
}
int findmin(int x,int cur){
    int ans=0x3f3f3f3f,index=0x3f3f3f3f,tmp;
    if (heap[cur].h<=x){
        if (ls(cur)<=num){
            tmp=findmin(x,ls(cur));
            if (tmp<=num&&(heap[ptr[tmp]].h<ans||(heap[ptr[tmp]].h==ans&&tmp<index))) {
                ans = heap[ptr[tmp]].h;
                index = tmp;
            }
        }
        if (rs(cur)<=num){
            tmp=findmin(x,rs(cur));
            if (tmp<=num&&(heap[ptr[tmp]].h<ans||(heap[ptr[tmp]].h==ans&&tmp<index))) {
                ans = heap[ptr[tmp]].h;
                index = tmp;
            }
        }
        return index;
    }
    else return heap[cur].n;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>num;
    for (int i=1;i<=num;++i) {
        cin>>heap[i].h;
        heap[i].n=i;
        ptr[i]=i;
    }
    for (int i=num;i>=1;--i)
        minheapify(i);
    while (cin>>cmd){
        if (strcmp(cmd,"findmin")==0){
            cin>>x;
            cout<<findmin(x,1)<<endl;
        }
        if (strcmp(cmd,"decrease")==0){
            cin>>x>>d;
            modify(x,d);
        }
    }
    return 0;
}

yyong119's solution 

#include <iostream>
#include <algorithm>
#define ERRORNUM 0x7fffffff
using namespace std;
const int SIZE = 100010;
int plane[SIZE];
pair<int, int> heap[SIZE];
int N;

void MinHeap(int pos) {

    pair<int, int> tmp;
    for (; pos > 1 && heap[pos >> 1] > heap[pos]; pos >>= 1) {
        tmp = heap[pos >> 1];
        heap[pos >> 1] = heap[pos];
        heap[pos] = tmp;
    }
}

void Maintain(int planeIndex, int decrease_height) {

    int pos = plane[planeIndex];
    pair<int, int> tmp;
    heap[pos].first -= decrease_height;
    for (; pos > 1 && heap[pos >> 1] > heap[pos]; pos >>= 1) {
        tmp = heap[pos >> 1];
        heap[pos >> 1] = heap[pos];
        heap[pos] = tmp;
        plane[heap[pos].second] = pos;
        plane[heap[pos >> 1].second] = pos >> 1;
    }
}

int FindMin(int min_height, int root_pos = 1) {

    if (root_pos > N) return ERRORNUM;
    if (heap[root_pos].first > min_height) return heap[root_pos].second;
    return min(FindMin(min_height, root_pos << 1), FindMin(min_height, root_pos << 1 | 1));
}

int main() {

    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> heap[i].first;
        heap[i].second = i;
        MinHeap(i);
    }
    for (int i = 1; i <= N; ++i) plane[heap[i].second] = i;
    char op[10];
    while (cin >> op) {
        if (op[0] == 'd') {
            int planeIndex, decrease_height;
            cin >> planeIndex >> decrease_height;
            Maintain(planeIndex, decrease_height);
        }
        else {
            int min_height;
            cin >> min_height;
            int planeIndex = FindMin(min_height);
            cout << planeIndex << '\n';
        }
    }
    return 0;
}