如题,只有subtask #1的第二个测试点过不了,其他所有测试点都能AC。
经assert,发现此测试点n=2,不知道是什么神奇的hack数据,求助各位神犇,悬赏1关注。
赛时第一份代码(大样例#4也过不去,输出14144,答案14151),WA on Subtask #1,#2,输出2,应为3。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
typedef long long ll;
const int _=1e5+10;
using namespace std;
int n;
ll x,p,q;
ll t[_];
template<typename tp>tp gcd(tp c,tp d){
if(!c||!d) return c^d;
while(d^=c^=d^=c%=d);
return c;
}// 应该没有问题
void test(){
printf("Day time:%lld,sleep time:%lld\n",x,p);
for(int i=1;i<=n;i++) printf("work #%d,time:%lld\n",i,t[i]);
}// 输出转换后的时间,调试用
template<typename tp>inline tp cil(tp c,tp d){
return c%d?c/d+1:c/d;
}// 返回 ceil(c/d)
int main(){
// freopen("E:\\task\\task4.in","r",stdin);
scanf("%d%lld%lld%lld",&n,&x,&p,&q);
// 为了避免浮点数精度误差,先将p/q约分,再令p=p*x,则前i天睡觉的小时数为p*i,同时将所有时间乘q,就可以把所有用到浮点的地方改成整数,考虑到会爆int,故全部改用long long。
ll Gcd=gcd(p,q);
p/=Gcd,q/=Gcd;p*=x;x*=q;
for(int i=1;i<=n;i++) scanf("%lld",&t[i]),t[i]*=q;
ll ld=0,ls=0;
// ld:last_day,已经经过的天数
// ls:last_sleep,从第1天到第ld天一共睡的小时数
for(int j=1;j<=n;){// j:当前在处理第j个任务
ll k=cil(p*ld+t[j]-ls,x-p);
// k:从第last_day+1天开始,再连续睡k-1天后,才能在第k天有足够的精力完成第j个任务。
// 形式化地,k是令last_sleep+k*x-t[j]>=p*(last_day+k)成立的最小的k
ls+=x*(k-1);
// 先把k-1天睡了。(
ld+=k;
// 时间到了第last_day+k天。
ll nd=x;
// nd:now_day,在这一天除做任务外,剩下能睡觉的时间
while(j<=n&&nd-t[j]>0&&(ls+nd-t[j]>=p*ld)) nd-=t[j],j++;
// 在这一天里,做工作,如果还有精力和时间,就尽量多干活,在不够睡之前停下。
ls+=nd;
// 睡觉。
}
printf("%lld\n",ld);
return 0;
}
在赛时,发现#4大样例过不了(属于subtask#3),果断为sub#3码暴力,同时发现nd-t[j]>0这一句不太好,改为nd-t[j]>=q(我也不太明白为什么),但sub#3其实没啥事,而sub#1,#2变成了TLE(
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
typedef long long ll;
const int _=1e5+10;
using namespace std;
int n;
ll x,p,q;
ll t[_];
template<typename tp>tp gcd(tp c,tp d){
if(!c||!d) return c^d;
while(d^=c^=d^=c%=d);
return c;
}
void test(){
printf("Day time:%lld,sleep time:%lld\n",x,p);
for(int i=1;i<=n;i++) printf("work #%d,time:%lld\n",i,t[i]);
}
template<typename tp>inline tp cil(tp c,tp d){
return c%d?c/d+1:c/d;
}
void brute(){// 暴力的思路和下面差不多,但是变成了枚举天数,因为保证t*i/x+p/q<=1,转换一下就是保证每天都有工作。
int Day=1,work=1;ll lastsleep=0;
for(Day=1;work<=n;Day++){
ll nowday=x;
if(lastsleep+nowday-t[work]<p*Day){lastsleep+=nowday;continue;}
while(work<=n&&nowday-t[work]>=q&&lastsleep+nowday-t[work]>=p*Day)
nowday-=t[work],work++;
lastsleep+=nowday;
}
Day--;
printf("%d\n",Day);
}
bool check(){
for(int i=1;i<=n;i++) if(t[i]+p>x) return 0;
return 1;
}
int main(){
// freopen("E:\\task\\task4.in","r",stdin);
scanf("%d%lld%lld%lld",&n,&x,&p,&q);
ll Gcd=gcd(p,q);
p/=Gcd,q/=Gcd;p*=x;x*=q;
for(int i=1;i<=n;i++) scanf("%lld",&t[i]),t[i]*=q;
ll ld=0,ls=0;
if(check()){brute();return 0;}
for(int j=1;j<=n;){
ll k=cil(p*ld+t[j]-ls,x-p);
ls+=x*(k-1);ld+=k;
if(ls<p*(ld-1)){ls+=x;continue;}
ll nd=x;
while(j<=n&&nd-t[j]>=q&&(ls+nd-t[j]>=p*ld)) nd-=t[j],j++;
ls+=nd;
}
printf("%lld\n",ld);
return 0;
}
在比赛结束后,用assert骗数据+特判才过,目前看来暴力没什么问题,锅出在main函数里面的那一坨。。。
特判代码就不放了,非伸手党,恳求大佬指点。