我是靠谱客的博主 魁梧帅哥,最近开发中收集的这篇文章主要介绍CodeForces - 514D (线段树+二分),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

An army of n droids is lined up in one row. Each droid is described by m integers a1, a2, …, am, where ai is the number of details of the i-th type in this droid’s mechanism. R2-D2 wants to destroy the sequence of consecutive droids of maximum length. He has m weapons, the i-th weapon can affect all the droids in the army by destroying one detail of the i-th type (if the droid doesn’t have details of this type, nothing happens to it).

A droid is considered to be destroyed when all of its details are destroyed. R2-D2 can make at most k shots. How many shots from the weapon of what type should R2-D2 make to destroy the sequence of consecutive droids of maximum length?

Input
The first line contains three integers n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 5, 0 ≤ k ≤ 109) — the number of droids, the number of detail types and the number of available shots, respectively.

Next n lines follow describing the droids. Each line contains m integers a1, a2, …, am (0 ≤ ai ≤ 108), where ai is the number of details of the i-th type for the respective robot.

Output
Print m space-separated integers, where the i-th number is the number of shots from the weapon of the i-th type that the robot should make to destroy the subsequence of consecutive droids of the maximum length.

If there are multiple optimal solutions, print any of them.

It is not necessary to make exactly k shots, the number of shots can be less.

Examples
input

5 2 4
4 0
1 2
2 1
0 2
1 3

output

2 2

input

3 2 4
1 2
1 3
2 2

output

1 3

Note
In the first test the second, third and fourth droids will be destroyed.

In the second test the first and second droids will be destroyed.

题目大意:给出n个机器人,每个机器人有m个属性,我们可以使用一个武器来破坏所有机器人的某一个属性,然后问我们最多开K枪的情况下,我们可以破坏的最长的连续机器人,然后输出我们的方案。

解题思路:我们观察得到m是很小的一个数(m<=5),所以我们可以用一个线段树来维护这m个数,然后我们二分枚举区间来得到这个区间中的每个属性的最大值,然后我们使得这个区间的机器人的所有属性都变为0,就需要开每个属性的最大值的和,判断一下这个值是否小于等于K即可。
但是打排位赛的时候题意读错了,本来一个很简单的二分加线段树,因为我题意都没读懂,就一直没有动手敲。
代码:

#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <queue>
//#include <random>
#include <time.h>
using namespace std;
#define int long long
#define ls root<<1
#define rs root<<1|1
const int maxn = 1e5 + 7;
//std::mt19937 rnd(time(NULL));
struct
{
int date[5];
int l, r;
}t[maxn<<2];
int n, m, ans[10], tmp[10], k;
void build(int root,int l,int r)
{
t[root].l = l, t[root].r = r;
if(l==r){
for (int i = 0; i < m;i++){
scanf("%lld", &t[root].date[i]);
}
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid+1, r);
for (int i = 0; i < m;i++)
t[root].date[i] = max(t[ls].date[i], t[rs].date[i]);
}
void query(int root,int l,int r)
{
if(t[root].l>=l && t[root].r<=r){
for (int i = 0; i < m;i++){
tmp[i] = max(tmp[i], t[root].date[i]);
}
return;
}
int mid = t[root].l + t[root].r >> 1;
if(l<=mid)
query(ls, l, r);
if(r>mid)
query(rs, l, r);
}
bool check(int len){
for (int i = 1; i + len <= n + 1;i++){
memset(tmp, 0, sizeof tmp);
query(1, i, i + len - 1);
int res = 0;
for (int j = 0; j < m;j++){
res += tmp[j];
}
if(res<=k)
return true;
}
return false;
}
signed main()
{
scanf("%lld%lld%lld", &n, &m, &k);
build(1, 1, n);
int l = 1, r = n;
while(l<=r){
int mid = l + r >> 1;
if(check(mid)){
memcpy(ans, tmp, sizeof tmp);
l = mid + 1;
}
else
r = mid - 1;
}
for (int i = 0; i < m;i++){
printf("%lld ", ans[i]);
}
}

最后

以上就是魁梧帅哥为你收集整理的CodeForces - 514D (线段树+二分)的全部内容,希望文章能够帮你解决CodeForces - 514D (线段树+二分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(41)

评论列表共有 0 条评论

立即
投稿
返回
顶部