30分TLE,我想知道为什么会超时

P1167 刷题

PT_get @ 2020-09-13 10:41:35

#include<bits/stdc++.h>
using namespace std;
#define MAX 5000+10

long long a[MAX];
long long f[MAX];
int n;
int yy1,m1,d1,h1,min1;
int yy2,m2,d2,h2,min2;
long long m;
char c,cc,ccc,cccc,ccccc;
int d[13]={0,31,59,90,120,151,181,212,243,273,304,334,365};

bool pd(int x)
{
    if((x%4==0 && x%100!=0) || x%400==0) return 1;
    else return 0;
}

int main(/*o(* ̄︶ ̄*)o*/)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d-%d-%d-%d:%d",&yy1,&m1,&d1,&h1,&min1);
    scanf("%d-%d-%d-%d:%d",&yy2,&m2,&d2,&h2,&min2);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) f[i]=a[i]+f[i-1];
    if(yy1==yy2)
    {
        m+=((d[m2-1]-d[m1-1]-d1+d2)*24-h1+h2)*60-min1+min2;
    }
    else
    {
        for(int i=yy1;i<=yy2;i++)
        {
            if(i==yy1) m+=(((d[12]-d[m1-1]-d1)*24-h1)*60-m1);
            else if(i==yy2) m+=(((d[m2-1]+d2)*24+h2)*60+m2);
                 else if(pd(i)) m+=366*24*60;
                      else m+=365*24*60;
        }
    } 
    int left=0,right=n+1,mid;
    while(left<right)
    {
        mid=(left+right)>>1;
        if(f[mid]<=m) left=mid;
        else right=mid-1;
    }
    printf("%d\n",left);
    return 0;
}

欢迎各位大佬帮忙解答


by Pethly_Cat @ 2020-09-13 10:52:01

@PT_get

 while(left<right)
    {
        mid=(left+right)>>1;
        if(f[mid]<=m) left=mid;
        else right=mid-1;
    }

改成

 while(left<right)
    {
        mid=(left+right)>>1;
        if(f[mid]<=m) left=mid+1;
        else right=mid-1;
    }

就好了


by PT_get @ 2020-09-13 11:04:53

@Pethly_Cat 不对啊,样例都过不去


by PT_get @ 2020-09-13 11:12:49

我改成

while(left<right-1)
{
    mid=(left+right)>>1;
    if(f[mid]<=m) left=mid;
    else right=mid-1;
}

80分WA


by HHHHHHuang @ 2021-06-07 21:12:22

m+=(((d[12]-d[m1-1]-d1)24-h1)60-m1) 不应该是min1吗?


|