| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1454 人关注过本帖
标题:【求助】新手,这个问题编了好久没有对,好心人帮忙看一下好吗?
只看楼主 加入收藏
xuiweide529
Rank: 1
等 级:新手上路
帖 子:2
专家分:5
注 册:2013-3-10
收藏
得分:0 
回复 20楼 xuiweide529
打错了,是减不是用除。
2013-03-10 03:12
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:5 
你的思路很乱,貌似是枚举每个开头,但是完全写错了= =
2013-03-10 07:40
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
回复 21楼 xuiweide529
数据量n<=100000,这个算法即使优化也需要计算n^2=10^12次,时间耗费太大
2013-03-10 07:41
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
程序代码:
#include <iostream>
using namespace std;

int s[100001],n,f,ans=0;

int main()
{
    cin>>n>>f;
    for (int i=1; i<=n; i++)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    
    for (int i=1,j=0; i<=n; i++)
    {
        while (s[i]-s[j]>f) j++;
        if (ans<i-j) ans=i-j;
    }
    
    cout<<ans<<endl;
    
//    system("pause");
}
        
2013-03-10 07:52
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
令s[i]=a[1]+a[2]+...a[i],则目标变为找到两个数i,j,使得s[i]-s[j]<=f且i-j最大

考虑到若i1<i2,则j1<=j2,所以每次枚举i的时候直接使用上次j的结果即可,由于i和j总共最多分别加n次,所以总的时间复杂度为O(n+n)=O(n)
2013-03-10 07:55
微笑微笑
Rank: 1
等 级:新手上路
帖 子:17
专家分:0
注 册:2013-3-10
收藏
得分:0 
回复 24楼 czz5242199
我是新手,代码就会用我程序里的那几个,你的我完全看不懂怎么办啊。。。。。
2013-03-10 09:05
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
回复 26楼 微笑微笑
我没用什么恨高深的代码啊,cin代表读入,cout代表输出,其他的和c一模一样
2013-03-10 09:35
tremere
Rank: 6Rank: 6
来 自:火星
等 级:侠之大者
帖 子:223
专家分:432
注 册:2013-3-11
收藏
得分:5 
我是菜鸟。我连你编的第一个头文件是啥子都不知道

极品菜鸟,来学习啦,啦啦啦啦啦啦啦。。。
2013-03-11 09:14
快速回复:【求助】新手,这个问题编了好久没有对,好心人帮忙看一下好吗?
数据加载中...
 
   



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

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