我是认真写的。。。。。。虽然看上去像乱敲的,,,代码有点丑大佬见谅,,,,,
by shuyingte @ 2018-12-27 20:48:36
我觉得这题WA也就罢了,可我实在想不明白为什么n*log(n)十万会TLE
by shuyingte @ 2018-12-27 20:56:31
而且连n=10都TLE
by shuyingte @ 2018-12-27 20:56:52
求助!!我又写了一篇,7WA3TLE!!!求大佬指点!!
```
#include<bits/stdc++.h>
#define N 100002
#define LL unsigned long long
using namespace std;
inline LL read(){
LL x=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
return x;
}
inline __int128 READ(){
__int128 x=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
return x;
}
struct data{
LL dis,tim;
int rk,magic;
bool operator <(const data &a)const{
return tim+magic<a.tim+a.magic;
}
}room[N];
multiset<data> S;//充当优先队列
data rank[N];//rank[i]表示距离第i名的data是哪个
bool use[N];//use[i]=true 表示排名为[i]个数选了没有
inline bool cmp(data A,data B){
return A.dis>B.dis;
}
int n,ans;
__int128 time_limit,sum;
int max_rank=1;
inline void update(){
ans--;
data tmp=*--S.end();
use[tmp.rk]=0;
S.erase(--S.end());
sum-=tmp.tim;
if(tmp.magic){
sum-=tmp.magic;
while(!use[max_rank])max_rank++;
data noip=*S.find(rank[max_rank]) ;
int t=max_rank;
do{
t++;
}while(!use[t]);
noip.magic=rank[max_rank].dis-rank[t].dis;
S.insert(noip);
}
}
int main(){
scanf("%d",&n);
ans=n;
time_limit=READ();
for(register int i=1;i<=n;i++)
room[i].dis=read(),room[i].tim=read(),sum+=room[i].tim;
sum+=room[n].dis;
sort(room+1,room+1+n,cmp);//距离从大到小
room[1].magic=room[1].dis-room[2].dis;
for(register int i=1;i<=n;i++)
S.insert(room[i]),
rank[i]=room[i],
use[i]=1,
room[i].rk=i;
while(sum>time_limit) update();
printf("%d\n",ans);
return 0;
}
```
by shuyingte @ 2018-12-28 08:11:12
曹,抄题解秒懂!
类似于《铺设道路》《积木大赛》
无语了。。。。我真是滞涨
此贴到此终结。
by shuyingte @ 2018-12-28 08:58:15