如何打印数组连续部分的第一个和最后一个元素?

Question

任务描述：在输入中，我们有 6 天的时间进行测量。

第一列是早晨的测量值 第二列是晚上的测量值

我们必须打印晚间测量高于早晨测量值的最长时间的索引(开始和结束)

我只想打印数组连续数组的第一个和最后一个元素的索引，例如：

阿尔是{1, 6, 3, 4, 5}

连续元素仅为：(3,4,5)第一个和最后一个元素是 ->(3,5)

#include <iostream>

using namespace std;

struct Measure {
int morning, evening;
};

int main()
{
Measure measures[300];
int n, firstResult[100];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> measures[i].morning >> measures[i].evening;
}
int counter = 0;
for (int i = 0; i < n; i++) {
if (measures[i].morning < measures[i].evening) {
counter++;
firstResult[counter] = i + 1;
}
}
for (int i = 1; i <= counter; i++) {
cout << firstResult[i] << " ";

}
cout << endl;
return 0;
}

输入：

6
100 120
200 122
170 190
100 222
150 155
75 60

输出应该是3和5的，因为数组从索引3rd到5th是连续的，但我的代码在输出中给出了1 3 4 5。 我怎么能只打印连续部分的第一个和最后一个元素。

Answer 1

我建议使用硬编码输入而不是通过cin读取，以便于测试和调试。并将std::vector用于动态大小的数组(= 直到运行时您才知道大小)：

std::stringstream ss{R"(100 120
200 122
170 190
100 222
150 155
75 60)"};
std::vector<Measure> measures;
Measure temp;
while (ss >> temp.morning >> temp.evening) measures.push_back(temp);

接下来，您应该实际找到连续的元素序列。在您的代码中，您只需计算morning < evening的所有元素，无论它们在数组中的哪个位置。您可以使用一个循环，其中使用标志来记住您是在连续序列内部还是外部。我强烈建议始终使用从 0 开始的索引。如果需要打印基于 1 的索引作为结果，您仍然可以为输出添加一个索引。

std::vector<contiguous_sequence> find_contiguous_sequences(const std::vector<Measure>& m){
std::vector<contiguous_sequence> result;
contiguous_sequence current;
bool inside = false;
for (size_t i = 0; i < m.size(); ++i){
if (m[i].morning < m[i].evening) {
if (inside) continue;
inside = true;                 // state change: outside -> inside       
current.begin = i;
} else {
if (inside) {                  // state change: inside outside
current.end = i;
inside = false;
result.push_back(current);
}
}
}
if (inside) {                  // check if the last element of the array was inside
current.end = m.size();
result.push_back(current);
}
return result;            
}

在这里，inside跟踪您是否在morning < evening元素的连续序列中。并且这些序列的开始和结束存储在result中。请注意，我曾经采用半开放区间惯例，即begin是序列中的第一个元素，而end是序列中最后一个元素之后的一个元素。当向量末尾有一个序列时，您需要考虑这一点。那么最后一个end不是向量中的元素。

使用上述输入调用此函数并打印其结果：

auto cs = find_contiguous_sequences(measures);
for (const auto& e : cs ) std::cout << e.begin << " " << e.end << "n";

结果在

0 1
2 5

我会留给你找到最大的序列并打印出来。

现场演示

Answer 2

您必须记住，您处于有效序列中，每次输入新的有效序列时，都必须重置计数器。此外，您必须只打印 firstResult 数组的 forst 和最后一个元素。代码可能如下所示

#include <iostream>
using namespace std;
struct Measure {
int morning, evening;
};

int main()
{
Measure measures[300];
int n, firstResult[100];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> measures[i].morning >> measures[i].evening;
}
int counter = 0;
bool counting = false;
for (int i = 0; i < n; i++) {
if (measures[i].morning < measures[i].evening) 
{
if (!counting) {
counting = true;
counter = 0;
}
firstResult[counter++] = i + 1;
}
else
{
counting = false;
}
}
if (counter > 0)
{
cout << firstResult[0] << " " << firstResult[counter - 1];
}
cout << endl;
return 0;
}