Skip to content

11290: 【原1290】灵机一动!

题目

题目描述

author: Xihu Zhang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1290

Description

Black Yellow Bar!

Yellow哥喜欢灵机一动。

在Yellow哥的家乡,有机房一条街,街上有很多机房。每所机房里都有一万个人在切题。Yellow哥刚刷完topcoder,准备出来逛逛。

机房一条街有N所机房。为了方便,每所机房都有一个非负整数坐标xi。Yellow哥的家坐标为0。

Yellow哥在街上移动的速度为1,即Yellow哥从x1到x2所耗费的时间为|x1-x2|。

每所机房的学生数量不同,ACM题目水平也良莠不齐。Yellow哥到达第i所机房后,他需要ti的时间想题,然后“灵机一动,带崩三路”,完成AK。

当然,Yellow哥可以只经过那所机房而不进入。

Yellow哥现在只有T个单位时间,过了T个时间后,Yellow哥就该赶着去打Codeforces了。

现在Yellow哥想知道,在T个单位时间内,他最多能带崩多少所机房。

Input Format

第一行两个数字N,T。

接下来N行,每行两个数字xi,ti.

Output Format

一个数Ans,表示Yellow哥最多能带崩的机房数量。

Sample Input

2 10
1 100
5 5

Sample Output

5

Sample Illustration

Yellow哥花5个单位时间经过第1所机房,走到第2所机房,花5个单位时间带崩这所机房。正好用了10个单位时间。

这也是最优方案,没有其它更优方案。

Hint

30%的数据:1≤N≤1024;

100%的数据:1≤N≤262144、0≤xi≤10^18、0≤ti≤10^9、0≤T≤10^18。

WashSwang's solution

#include <iostream>
using namespace std;
long long T,x[300000],walktime,aktime,ans;
int heap[600000],num,n,t[300000];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
void maxheapify(int x){
    int s=x;
    while (true){
        if (ls(x)<=num&&heap[ls(x)]>heap[s]) s=ls(x);
        if (rs(x)<=num&&heap[rs(x)]>heap[s]) s=rs(x);
        if (s!=x){
            swap(heap[s],heap[x]);
            x=s;
        }
        else break;
    }
}
void push(int x){
    heap[++num]=x;
    int now=num;
    while (now>1&&heap[now]>heap[now>>1]){
        swap(heap[now],heap[now>>1]);
        now>>=1;
    }
}
int pop(){
    int ret=heap[1];
    heap[1]=heap[num];
    num--;
    maxheapify(1);
    return ret;
}
void qsort(int l,int r){
    if (l+1>=r) return;
    int i=l,j=r-1,keyt=t[l];long long keyx=x[l];
    while (i<j){
        while (i<j&&x[j]>=keyx) --j;
        if (i<j){swap(x[i],x[j]);swap(t[i],t[j]);++i;}
        while (i<j&&x[i]<=keyx) ++i;
        if (i<j){swap(x[i],x[j]);swap(t[i],t[j]);--j;}
    }
    x[i]=keyx;
    t[i]=keyt;
    qsort(l,i);
    qsort(i+1,r);
}
int main() {
    scanf("%d%lld",&n,&T);
    for (int i=0;i<n;++i)
        scanf("%lld%d",&x[i],&t[i]);
    qsort(0,n);
    for (int i=0;i<n;++i) {
        walktime = x[i];
        while (num > 0 && walktime + aktime + t[i] > T && heap[1]>t[i]) aktime -= pop();
        if (aktime + walktime + t[i] <= T) {
            aktime += t[i];
            push(t[i]);
            if (num > ans) ans = num;
        }
    }
    printf("%lld",ans);
    return 0;
}

yyong119's solution

#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAX_N 300010
using namespace std;
int n, ans, heap_size;
long long T;
struct Node {
    long long x, t;
} a[MAX_N];
int gr_heap[MAX_N];
inline long long read() {
    char ch = getchar(); long long res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    // return res * flag;
    return res;
}
inline bool cmp(const Node &p, const Node &q) {
    return p.x < q.x;
}
int main() {
    n = read(); T = read();
    for (register int i = 1; i <= n; ++i)
        a[i].x = read(), a[i].t = read();
    sort(a + 1, a + n + 1, cmp);
    make_heap(gr_heap, gr_heap + heap_size, less<int>());
    for (register int i = 1; i <= n; ++i) {
        T -= a[i].x - a[i - 1].x;
        while (heap_size > 0 && T < 0) {
            T += gr_heap[0];
            pop_heap(gr_heap, gr_heap + heap_size--, less<int>());
        }
        if (T < 0) break;
        if (T >= a[i].t) {
            T -= a[i].t;
            gr_heap[heap_size++] = a[i].t;
            push_heap(gr_heap, gr_heap + heap_size, less<int>());
            ans = max(ans, heap_size);
        }
        else if (heap_size > 0 && a[i].t < gr_heap[0]) {
            T += gr_heap[0];
            pop_heap(gr_heap, gr_heap + heap_size, less<int>());
            T -= a[i].t;
            gr_heap[heap_size - 1] = a[i].t;
            push_heap(gr_heap, gr_heap + heap_size, less<int>());
        }
    }
    printf("%d", ans);
    return 0;
}