求助sub#1第二个测试点
查看原帖
求助sub#1第二个测试点
663681
C_liar楼主2022/9/4 21:40

如题,只有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函数里面的那一坨。。。

特判代码就不放了,非伸手党,恳求大佬指点。

2022/9/4 21:40
加载中...