外星人已经到达地球并且一切都和谐相处，两个种族可以生活在一起。但是，一个特定的女性外星人不想
在去大学的路上看到人类，外星人必须像每个人类一样使用火车。但是她可以选择任何一个火车站
，这样她看到的人不会超过\ $ B \ $，但是，外星人希望
尽可能走火车。请帮她完成这个
任务。
输入：
您将收到一个整数\ $ T \ $，表示
测试用例的数量，那么下一行将包含两个整数\ $ A_t \ $
\ $ B_t \ $，其中\ $ A_t \ $和\ $ B_t \ $是
火车中的车站数（\ $ 1 \ leq A_t \ leq100,000 \ $）和
外星人希望看到的最大人数（\ $ 1 \ leq B_t \ leq10,000,000 \ $），在
之后，包含\ $ A_t \ $整数且由单个空格分隔的行
表示外星人可以在\ $ A_t（i）\ $
站中找到的人数。 （每个站点将有多达100人。）
输出：
您的输出应包含\ $ T \ $对数字，表示
示例输入/输出：
输入：
/>
1
5 100
20 15 30 80 100
输出
65 3
我的解决方案只是在时间限制的边界上。我想知道我的代码在竞争性编程和C / C ++语言中的任何改进。
如何加快I / O速度并缩短代码？ />
#include <cstdio>
#include <deque>
using namespace std;
int main()
{
int t,siz;
scanf("%d",&t);
long long int at,bt,sum=0,max=0,maxsum=0,peep=0;
deque<int> people;
while(t--){
sum=max=maxsum=peep=0;
people.clear();
scanf("%lld%lld",&at,&bt);
while(at--){
scanf("%lld",&peep);
people.push_back(peep);
if(sum+peep<=bt)
{
sum+=peep;
}
else{
siz=people.size()-1;
if(max==siz){
maxsum=maxsum<sum?maxsum:sum;
}
else if(max<siz){
maxsum=sum;
max=siz;
}
sum+=peep;
while(sum>bt){
sum-=people.front();
people.pop_front();
}
}
}
siz=people.size();
if(max==siz){
maxsum=maxsum<sum?maxsum:sum;
}
else if(max<siz){
maxsum=sum;
max=siz;
}
printf("%lld %lld\n",maxsum,max);
}
return 0;
}
#1 楼
您可能是正确的，该程序的主要性能瓶颈是I / O。因此，您可以考虑执行以下一项或多项操作：一次读取一行
尝试使用
fgets一次读取一行，然后使用sscanf解析缓冲区中的数字。这可能对于读取火车站线路特别有用。滚动自己的
scanf替代品scanf功能有用但通用。一个更快的专用sscanf替换功能，它也很少执行错误检查，它是： >现在，您的代码使用了相对较高级别的scanf函数，但是使用较低级别的调用（例如read）然后解析内存中的行，可能会发现性能有所提高。评论
\ $ \ begingroup \ $
+1用于较低级别的IO；对于大输入，这会带来比某些人想像的要大得多的性能提升。
\ $ \ endgroup \ $
–分裂
14年8月8日在16:10
#2 楼
不要使用using namespace std 这里不是什么大问题，但是
using namespace std;通常被认为是不好的做法。 /> 您可以使用流运算符来代替
scanf的使用。使用您最喜欢的文本编辑器来解决此问题。变量。在此阶段，您的代码如下：
#include <iostream>
#include <deque>
int main()
{
int t;
std::cin >> t;
while(t--){
std::deque<int> people;
long long int at,bt,sum=0,max=0,maxsum=0;
std::cin >> at >> bt;
while(at--){
long long int peep;
std::cin >> peep;
people.push_back(peep);
if(sum+peep<=bt)
{
sum+=peep;
}
else{
int siz=people.size()-1;
if(max==siz){
maxsum=maxsum<sum?maxsum:sum;
}
else if(max<siz){
maxsum=sum;
max=siz;
}
sum+=peep;
while(sum>bt){
sum-=people.front();
people.pop_front();
}
}
}
int siz=people.size();
if(max==siz){
maxsum=maxsum<sum?maxsum:sum;
}
else if(max<siz){
maxsum=sum;
max=siz;
}
std::cout << maxsum << " " << max << std::endl;
}
return 0;
}
评论
\ $ \ begingroup \ $
由于OP的目标不是提高速度（更通常的可维护性），所以我不同意所有在尽可能小的范围内定义变量。这样做会产生构造函数/析构函数调用的开销。在外部范围内声明人员并调用people.clear（）的原始设计似乎更合适。
\ $ \ endgroup \ $
–马丁·约克
2014年8月8日在11:15
\ $ \ begingroup \ $
由于最终目标是速度，因此请记住要通过调用std :: ios_base :: sync_with_stdio（false）;来取消同步C和C ++流（这使C / C ++流具有同等的速度）。请参见C和C ++中执行时间的差异。
\ $ \ endgroup \ $
–马丁·约克
2014年8月8日在11:18
\ $ \ begingroup \ $
好吧，公平地说，我进行了一些小的改动，以便更好地理解以前用来改进它的算法。在这种挑战下，真正的改进来自算法的变化，而不是来自微优化。话虽这么说，我对sync_with_stdio一无所知，所以很高兴今天学到了一些东西。
\ $ \ endgroup \ $
– SylvainD
2014年8月8日12:57
\ $ \ begingroup \ $
@LokiAstari在较小范围内移动变量并不一定会使程序效率降低。它通常会影响程序的语义，而不是优化后生成的实际代码。至于构造器/解构器，每个测试用例只能得到一个新的/删除的内容，而当前代码每次内部迭代都会有一个调整大小的操作（我已经在答案中删除了）。
\ $ \ endgroup \ $
–iavr
2014年8月9日在0:10
\ $ \ begingroup \ $
@ivar：我只是从速度角度看这个问题。没有第一时间就不应该放弃微观优化。通过将人员结构移动到一个作用域级别，您将clear（）交换为两个调用deque
\ $ \ endgroup \ $
–马丁·约克
2014年8月9日在3:23
#3 楼
关于性能，我没有什么要补充的，但是我有一些建议，以便您的程序更易于阅读。而且易于阅读的程序通常更易于理解，因此也易于改进：由于您要在
std::deque的末尾添加元素并将其从前面删除，我想您真正需要的是std::queue。由于std::queue使用std::deque，因此不会提高任何性能，但可以使代码更整洁。只需将std::deque替换为std::queue，并将push_back和pop_front操作替换为push和pop即可。实际上，这又可以进行间接操作，但是所有操作都应内联，因此，这种小的包装程序不应使您的代码变慢。您的代码缺少空格。您应该在使代码更具可读性的位置添加空格，通常是在表达式中的二进制运算符周围。
这段代码：
maxsum=maxsum<sum?maxsum:sum;
可以替换为以下内容：
maxsum = std::min(maxsum, sum);
应该不会有任何性能上的好处，但也不会有任何性能上的损失。
std::min可能使用三进制，并且编译器会内联对std::min的调用。老实说，它使代码更具可读性；由于您在此处使用的是名为maxsum的变量，因此我一开始就确信您正在执行的操作是最大操作。显式使用std::min可以避免这种可能的误解。return 0;的末尾不需要main。如果它到达main的末尾而没有找到任何return语句，则它将由编译器自动添加。您只会提高可读性。而且，由于我想重复一遍：您的代码越可读，越容易理解，就越有可能得到改进。评论
\ $ \ begingroup \ $
“您不需要在main的末尾返回0；如果编译器到达main的末尾而没有找到任何return语句，它将由编译器自动添加。”这完全取决于您使用哪个编译器。例如，Visual Studio会因为您的懒惰而大喊大叫。
\ $ \ endgroup \ $
–法老王
2014年8月9日11:31
\ $ \ begingroup \ $
@Pharap考虑到Visual Studio（2013CTP）的在线示例是一个简单的Hello World程序，它不会显式返回main的任何内容，因此这似乎很奇怪。而且它不会对我大喊大叫。
\ $ \ endgroup \ $
–莫文
2014年8月9日在11:41
#4 楼
您的代码是main（）中的一个重要功能。有意义的描述。我实际上不了解问题或您要使用的算法来解决它。
我会说使用流而不是scanf / printf。我怀疑是I / O使它变慢了。更可能是算法。
#5 楼
作为一种算法，对我来说它看起来正确且有效。做得好。作为一个程序，这是我重新编写它的方式：
#include <iostream>
#include <vector>
namespace test {
using namespace std;
struct alien
{
int max_sum, max_length;
void update(int sum, int length)
{
if (max_length == length)
max_sum = min(max_sum, sum);
else if (max_length < length)
{
max_sum = sum;
max_length = length;
}
}
alien()
{
int cases;
cin >> cases;
while (cases--)
{
int stations, max_people;
cin >> stations >> max_people;
vector<int> people(stations);
for (auto& p: people)
cin >> p;
int sum = 0;
max_sum = max_length = 0;
auto enter = people.begin(), leave = enter;
while (leave != people.end())
{
int prev_sum = sum;
if ((sum += *leave++) <= max_people)
continue;
update(prev_sum, leave - enter);
while (sum > max_people)
sum -= *enter++;
}
update(sum, leave - enter);
cout << max_sum << " " << max_length - 1 << endl;
}
}
};
} // namespace test
int main() { test::alien(); }
它可能比您的行长代码，但结构更清晰，冗余程度更低，并且可能更容易遵循。尽可能接近其使用。我为了所有方便而保留了
using namespace std，但仅保留在我自己的命名空间test中，因此不会造成任何危害。请注意，对于给定的边界，您不需要long long。我已将输入读数与实际计算分开。我已经将所有输入预先存储在向量
people中，此后不必重新调整大小，因为我通过迭代器enter，leave来指代其两端，两者都向前移动。这将对性能产生影响。差异leave - enter是我们的外星人旅行过的车站数量。因为leave实际上是最后一个位置，所以我们在打印时减去了1。为了不传递太多参数，我将状态保留在两个变量update和max_sum中。因此，现在所有内容都在max_length中，其构造函数将进行实际计算。我更喜欢在
class alien的循环中间进行中断，以避免产生过多的嵌套范围。更新continue之前我不检查;我只是将其先前的值保留在sum中，因此仅添加了一个。当然，无论如何，这都是优化器的工作。可以使用
prev_sum，std::accumulate等标准算法以及lambda重写所有内容而无需循环。在这方面，我还没有尝试过变得聪明，更接近您的代码。评论
\ $ \ begingroup \ $
基本上可以在构造函数中执行所有操作吗？ I / O和所有？ ：P
\ $ \ endgroup \ $
– cHao
2014年8月10日在11:04
\ $ \ begingroup \ $
“我尽可能使用了现代的高级C ++约定”将所有内容都放入构造函数中绝对不是“现代的高级C ++约定”。并使用命名空间std; ...
\ $ \ endgroup \ $
– L. F.
19年8月1日在5:42
#6 楼
前一段时间，我已经开始编写轻量级的仅快速io标头库。在spoj之类的比赛中非常有用。这只是我工作的开始（我不需要很多时间），但是您可以尝试一下（只需在开始时复制源代码并使用）：https：// github .com / adamf88 / Algorithms / blob / master / fastio.h
我对代码的优化（所有优化均为低级）：
使用双端队列，我使用了具有最大大小的简单数组来避免内存分配。代码并不像以前那样简单，我不得不添加两个新变量来手动管理队列（变量
begin和end）。我将
long long类型更改为unsigned int（检查任务限制后就足够了）我没有使用
cin/cout，而是创建了一些函数来读取基于unsigned int函数的fread值，并且使用最简单的方法进行了解析。 fread甚至比scanf还要快。我手动选择的缓冲区大小。我的解决方案需要0.01毫秒：
#include <stdio.h>
//---- fast io begin
#define BUF_SIZE 4000
char bufor[BUF_SIZE + 1 + 30];
char *buf_pointer;
char *end_pointer;
bool end_of_buffer()
{
return buf_pointer == end_pointer;
}
void init()
{
buf_pointer = bufor;
int readed = fread(bufor, 1, BUF_SIZE, stdin);
end_pointer = bufor + readed;
if (readed)
{
--end_pointer;
//read last number to end
while ((*end_pointer & 16) && readed)
{
++end_pointer;
readed = fread(end_pointer, 1, 1, stdin);
}
if (*end_pointer & 16)
{
++end_pointer;
*end_pointer = ' ';
}
//read white spaces
for (; (*buf_pointer & 16) == false;)
{
++buf_pointer;
if (buf_pointer >= end_pointer)
{
init();
}
}
}
}
void read_uint(unsigned& l)
{
char *data = buf_pointer;
l = 0;
while (*data & 16)
{
l *= 10;
l += *data & 15; //-40
++data;
}
//read white spaces
for (; (*data & 16) == false;)
{
++data;
if (data >= end_pointer)
{
init();
data = buf_pointer;
}
}
buf_pointer = data;
}
//---- fast io end
unsigned int q[100011];
int main()
{
init();
unsigned int n;
read_uint(n);
while (n--)
{
unsigned int a, b, begin = 0, end = 0;
unsigned int best_sum = 0, cur_sum = 0, best_len = 0;
read_uint(a);
read_uint(b);
while (a--)
{
read_uint(q[end]);
cur_sum += q[end];
++end;
while (cur_sum > b)
cur_sum -= q[begin++];
int q_size = end - begin;
if (best_len < q_size)
{
best_len = q_size;
best_sum = cur_sum;
}
else if (q_size == best_len && best_sum > cur_sum)
{
best_sum = cur_sum;
}
}
printf("%u %u\n", best_sum, best_len);
}
}
评论
\ $ \ begingroup \ $
如果希望提供自己的实现，则还必须说明它如何根据OP的代码进行改进。否则，它将被视为无答案。
\ $ \ endgroup \ $
– Jamal♦
15年5月18日在20:45
评论
使用空格，例如maxsum <总和？ maxsum：总和而不是maxsum大声笑，我认为这个问题与XCOM有关：未知的敌人:-)