问题标题: 酷町堂:3007 晾衣服 5个点TLE超时

0
0
已解决
周俊豪
周俊豪
高级光能
高级光能
(贪心)
#include<iostream>
#include<algorithm>
using namespace std;
int a[101000];
bool cmp(int a,int b){
    return a>b;//从大到小排效率最高
}
int main(){
    int n,c,b;
    cin>>n>>c>>b;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n,cmp);
    int sum=0;//计时间
    for(int i=1;i<=n;i++){
        if(a[i]>0){
            a[i]=a[i]-c-b;//对大于0湿度的衣服做晾干(自然晾干和烘干)
            sum++;
        }
        for(int j=i+1;j<=n;j++){
            a[j]=a[j]-c;//其他衣物自然晾干
        }
    }
    cout<<sum;
    return 0;
} 

5个点AC,5个点TLE(是不是因为双重循环?)

求大佬解答,怎样才能不超时?


0
已采纳
舒航
舒航
新手守护
新手守护

这个题目不是贪心!!!

另外你循坏也有问题!

for(int j=i+1;j<=n;j++)
{
      a[j]=a[j]-c;//其他衣物自然晾干
}

这个地方,我先问你能保证一件衣服一次循环后能被晒好吗

所以j=i+1改为j=1

然后再做个判断

或者:

你前面不减c

这里就不用做判断了。

 

总之你看范围( 1 ≤ 湿度, A , B ≤ 50000 , 1 ≤ N ≤ 50000 )

这么大用贪心绝对超时啊!!!

0
我要回答