验证中...
本周日【珠海源创会】一起聊聊:PingCAP分布式事务、支付宝移动端实践、GSBN技术框架选型,点此报名占座
语言: C/C++
分类: 算法分析
最后更新于 2018-11-09 22:53
luogu_p1360.cpp
原始数据 复制代码
// cow 信息结构体
struct cow_entry
{
// 记录 cow 在原输入序列中的位置
int index;
// 初始化为全 0
int feature[30] = {};
};
// 重载 < > == != 比较运算符用于快速排序 cow_entry
bool operator<(const cow_entry &left, const cow_entry &right)
{
// 组合条件排序
for (int i = 30 - 1; i >= 0; i--)
{
// 优先比较 feature 的高位
if (left.feature[i] > right.feature[i]) return false;
// 再比较 feature 的低位
if (left.feature[i] < right.feature[i]) return true;
}
// 最后比较index
return left.index < right.index;
}
bool operator>(const cow_entry &left, const cow_entry &right)
{
// 组合条件排序 同上
for (int i = 30 - 1; i >= 0; i--)
{
if (left.feature[i] < right.feature[i]) return false;
if (left.feature[i] > right.feature[i]) return true;
}
return left.index > right.index;
}
bool operator==(const cow_entry &left, const cow_entry &right)
{
// feature 完全相同的认为相等
for (int i = 0; i < 30; i++)
{
if (left.feature[i] != right.feature[i]) return false;
}
return true;
}
bool operator!=(const cow_entry &left, const cow_entry &right)
{
return !(left == right);
}
void golden_balanced_lineup()
{
cout << "Input:" << endl;
int n; // cow 数目
int m; // feature 位数
cin >> n >> m;
cow_entry *data = new cow_entry[n + 1];
for (int i = 0; i < n; i++)
{
// 读入各个 cow 的数据
int featureData;
cin >> featureData;
data[i].index = i; // 记录原始位置下标
// 拆分 feature 的各个二进制位为单独整数 并累加
for (int featureIdx = 0; featureIdx < m; featureIdx++)
{
if (i > 0)
{
// 将前一个 cow 的 feature 加到当前 cow 的 feature 上面 实现累加
data[i].feature[featureIdx] = data[i - 1].feature[featureIdx] + (featureData & 1);
}
else
{
// 第一个 cow 无需累加
data[i].feature[featureIdx] = (featureData & 1);
}
// 去掉已经使用过的二进制位
featureData >>= 1;
}
// 完成了累加后 对 balanced range 的起始点l与结束点r
// 有 data[r].feature[?] == data[l].feature[?] + k
}
// 问题简化为找到满足 data[r].feature[?] == data[l].feature[?] + k
// 的最大 r - l 的值
// 对各个 cow 的所有 feature 减去最低位的feature (feature[0])
for (int i = 0; i < n; i++)
{
for (int featureIdx = m - 1; featureIdx >= 0; featureIdx--)
{
data[i].feature[featureIdx] -= data[i].feature[0];
}
}
// balanced range 的起始点l与结束点r 满足
// data[r].feature[0] == data[l].feature[0] + k
// data[r].feature[i] == data[l].feature[i] + k
// 则有 data[r].feature[i] - data[r].feature[0] == data[l].feature[i] - data[l].feature[0]
// 完成了减去后
// 有 data[r].feature == data[l].feature
// 问题简化为找到满足 data[r].feature == data[l].feature
// 的最大 r - l 的值
// 补充所有 feature 均为 0 的初始状态 避免一些遗漏的情况
data[n].index = -1;
// 对所有 cow 进行快速排序
// 使得 data[r].feature == data[l].feature 的 cow 靠在一起
quick_sort(data, n + 1);
// 遍历排序后的cow数组
// 找到满足 data[r].feature == data[l].feature
// 的最大 r - l 的值
int max = 0;
cow_entry *last = data;
for (int i = 0; i < n + 1; i++)
{
// 满足 data[r].feature == data[l].feature
if (data[i] == *last)
{
// 记录最大 r - l 的值
int max_tmp = data[i].index - last->index;
if (max_tmp > max)
max = max_tmp;
}
else
{
last = data + i;
}
}
cout << endl << "Output:" << endl << max << endl;
}

评论列表( 0 )

你可以在登录后,发表评论

搜索帮助

12_float_left_people 12_float_left_close