| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 987 人关注过本帖
标题:时间超限的题,求帮忙优化
只看楼主 加入收藏
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
结帖率:92%
收藏
已结贴  问题点数:20 回复次数:6 
时间超限的题,求帮忙优化
图片附件: 游客没有浏览图片的权限,请 登录注册

这个代码能成功运行,但是时间超限,用的暴力计算法,求大佬提供优化算法,谢谢~
#include<stdio.h>
#include<stdlib.h>
int main(void){
  int T,n,m,i,k,sum=0,min,a[100000];
  scanf("%d",&T);
  while(T--){
      min=100001;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    for(i=0;i<n;i++){
        k=0;
        while(sum<m&&(i+k<n)){
          sum+=a[i+k];
          k++;
      }
        if(k<min&&sum>=m) min=k;
        sum=0;
    }
    if(min!=100001) printf("%d\n",min);
    else printf("0\n");
}
  return 0;
}
        
   
搜索更多相关主题的帖子: 时间 优化 sum min scanf 
2018-05-08 11:30
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:14 
https://bbs.bccn.net/thread-485587-1-1.html###

参考这个贴的第一个问题~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-08 12:31
nosnoy
Rank: 9Rank: 9Rank: 9
来 自:mcu
等 级:贵宾
威 望:14
帖 子:541
专家分:1178
注 册:2016-9-17
收藏
得分:6 
回复 2楼 九转星河
这个和你那个贴题意好像不一致
你那个给题是只有两个数
这个是0-n个数
先排序 再加?

穷举是最暴力的美学
2018-05-09 12:15
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 3楼 nosnoy
sum 递增~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-09 12:59
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 4楼 九转星河
不是很懂,大佬能再解释一下么?我也觉得两个题不一样
2018-05-09 15:26
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 5楼 青蝶
大意就是说求连续区间和大于等于k的最小区间段~

可以先把输入数组转化成前缀和的形式,如果没有负数那数据必然是非递减的~
这样就变成求两个差的值大于等于k的最小区间了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-09 17:34
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 6楼 九转星河
通过OJ了,感动~谢谢大佬帮忙~
2018-05-09 21:36
快速回复:时间超限的题,求帮忙优化
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021006 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved