@zimenglan
2014-11-01T12:16:04.000000Z
字数 1304
阅读 1005
1046 Plane Spotting
sicily
algorithm
给出一个长度为N的非负整数序列(所有数不超过200),还有两个整数M和K,求前M个最优的长度不小于K的连续子序列。
连续子序列的优先级如何比较
平均值大的序列优于平均值小的
长度大的序列优于长度小的
结束位置靠前的序列优于结束位置靠后的
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
struct nodes
{
/* data */
float averNum;
int len;
int lastIdx;
};
// note double or float has no ==
const float inf = 1e-9;
const int N = 305;
float myAbs(const float a, const float b) {
float diff = a - b;
if(diff < 0) {
diff = 0 - diff;
}
return diff;
}
int myMin(const int a, const int b) {
return a < b ? a : b;
}
bool cmp(const nodes& a, const nodes& b) {
if(a.averNum - b.averNum > inf) {
return true;
} else if(myAbs(a.averNum, b.averNum) < inf) {
if(a.len > b.len) {
return true;
} else if(a.len == b.len) {
if(a.lastIdx < b.lastIdx) {
return true;
}
}
}
return false;
}
int main() {
int T;
cin >> T;
for(int t = 0; t < T; t++) {
int n, m, k;
cin >> n >> m >> k;
int nums[N];
for(int i = 0; i < n; i++) {
cin >> nums[i];
}
//
std::vector<nodes> planes;
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = i; j < n; j++) {
sum += nums[j];
int len = j - i + 1;
// min size
if(len >= k) {
float averNum = sum / (len + 0.);
nodes pn;
pn.len = len;
pn.averNum = averNum;
pn.lastIdx = j + 1;
planes.push_back(pn);
}
}
}
int size = planes.size();
sort(planes.begin(), planes.end(), cmp);
size = myMin(size, m);
for(int i = 0; i < size; i++) {
if(i == 0) {
std::cout << "Result for run " << t + 1 << ":" << std::endl;
}
std::cout << planes[i].lastIdx - planes[i].len + 1 << "-" << planes[i].lastIdx << std::endl;
}
}
return 0;
}