2 solutions

  • 0
    @ 2025-3-10 15:55:00

    思路

    这道题因为其他原因导致数据很水,暴力都能过。我这里提供最开始的想法。用二分去写。 二分答案,对每一个时间t,确定到t可以观察到多少个星星闪耀。 然后这里有三种情况 三种情况:

    1:第i个星星开始时间大于t,直接跳过。

    2:开始时间在l和t之间,

    3:开始时间t小于l

    ac code

    #include<bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    const int N = 1e5 + 10;
    int n;
    LL a[N],b[N],l,r,tgt;
    bool check(LL x)
    {
    	LL cnt = 0;
    	for(int i = 1;i <= n;++ i)
    	{
    		if(a[i] > x)continue;//还没开始闪
    		if(a[i] <= x && a[i] >= l)//我当时都忘了还要大于l
    		{
    			cnt += (x - a[i])/b[i] + 1;
    			if(cnt >= tgt)return true;
    		}
    		else {
    			cnt += (x - a[i])/b[i] - (l - 1 - a[i])/b[i];
    			if(cnt >= tgt)return true;
    		} 
    	}
    	return false;
    }
    int main ()
    {
    	cin >> n;
    	for(int i = 1;i <= n;++ i)
    	{
    		cin >> a[i];//开始时间 
    	}
    	for(int i = 1;i <= n;++ i)
    	{
    		cin >> b[i];//周期	
    	} 
    	cin >> l >> r >> tgt;
    	LL l1 = l;
    	LL r1 = r;
    	while(l1 < r1)//二分左 
    	{
    		LL m = (l1 + r1) >> 1;
    		if(check(m))r1 = m;
    		else l1 = m + 1; 
    	}
    	check(l1) ? cout << l1 : cout << "-1"; 
    
    	return 0;
    }
    
    
    • 0
      @ 2024-12-8 14:13:55
      #include<cstdio>
      typedef long long ll;//不开long long 见祖宗。。。
      ll l,r,c,start ;
      ll  n ,a[100005],b[100009];
       bool check(ll x)//一定要注意!!!不要转换类型错了!!!
      {
      	ll sum = 0;
      	for(int i = 1;i <= n;i++)
      	{
      		if(b[i] > x)continue;
      	    else if(b[i] < start)
      		{
      			sum +=  (x - b[i])/a[i] - (start - 1 - b[i])/a[i];//start应该包含在里面,减去start-1以及前的区间
      		}
      		else sum += (x-b[i])/a[i] + 1;
      		//加一是当时开始亮的时候也要算一次
      		
      		if(sum >= c)return true;
      	}
      	
      	return false;
      }
      int main()
      {
      	
      	scanf("%lld",&n);
      	for(int i = 1;i <= n;i++)
      	{
      		scanf("%lld",&b[i]);
      	}
      	for(int i = 1;i <= n;i++)
      	{
      		scanf("%lld",&a[i]);
      	}
      	
      	
      	scanf("%lld%lld%lld",&l,&r,&c);
      	start = l;
          ll mid = 0;//救命,开的int一不小心就超时,改了我好久,可恶。。。。
      	while(l < r)//这里是一个从小到大的隐藏条件
      	{//举个例子:其中check(l+3)表示从l——l+3,这个区间里面的计数
      	 //并且,因为是闪一下记一次,check(l+4)肯定是不小于check(l+3)的
      	  //所以这一定是个递增的序列,我们就可以用二分啦!!!
      		 mid = l+ r>>1;
      		if(check(mid))r = mid;
      		else l = mid+1;
      		
      	}
      	if(check(l))printf("%lld",l);//判断一下这个数是否 >=c 
      	else puts("-1");
      	return 0;
      }
      
      • 1

      Information

      ID
      7004
      Time
      500ms
      Memory
      256MiB
      Difficulty
      8
      Tags
      # Submissions
      163
      Accepted
      21
      Uploaded By