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;
}