51 nod 1521 一维战舰 时间复杂度O(n),同 Codeforces 567D. One-Dimensional Battle Ships 有详细注释

题目:51nod:

51 nod 1521 一维战舰 时间复杂度O(n),同 Codeforces 567D. One-Dimensional Battle Ships 有详细注释

题目Codeforces:

51 nod 1521 一维战舰 时间复杂度O(n),同 Codeforces 567D. One-Dimensional Battle Ships 有详细注释

题目注意到两个战舰不能挨在一起就可以了。

// 每一段
struct node{
int left; // 段的左端点
int right; // 段的右端点
int length; // 段长度
int ship; // 段最大容纳战舰数
}arr[];

每一段可容纳战舰数:

ship*a + (ship - 1) <= length;   -->   ship = (length+1) / (a+1);(舍去小数部分)

构造出这么一个数据结构就简单了。

现在还有一个问题:找到说miss的点所在段还需要时间,就算是二分查找也需要O(log(n)),加上遍历的O(n),时间复杂度O(n*log(n))。

         可不可能会超时呢?我认为有可能,所以保险起见,我用了一个数组index[i]表示第i个点所在的段,用空间换时间,比较值。

一次就AC了,思路就这么多,上代码把:

#include <bits\stdc++.h>
using namespace std;
typedef long long ll; // 每一段
struct node{
int left; // 段的左端点
int right; // 段的右端点
int length; // 段长度
int ship; // 段最大容纳战舰数
}arr[];
int len = ; // 段的数量 int index[]; // 每一个点所处的段 int n,k,a,m;
int miss; // 每一次说miss的位置。 int sumShip = ; // 现阶段可容纳最多战舰数 // 获取某段可容纳最大战舰数量
int maxShip(node node1){
return (node1.length+)/(a+);
} //初始化
void init(){
arr[].left = ;arr[].right = n;
arr[].length = arr[].right - arr[].left + ;
arr[].ship = maxShip(arr[]);
sumShip = arr[].ship;
len = ;
} //更新段
void updataNode(int miss){
int con = index[miss]; // miss位置所在段
node* x = &arr[con]; //取出这个段
int shipNum = x->ship; arr[len].left = miss+;
arr[len].right = x->right;
arr[len].length = arr[len].right - arr[len].left + ;
arr[len].ship = maxShip(arr[len]);
replace(index+arr[len].left,index+arr[len].right+ , con ,len); // 将其中一部分所在段改变 x->right = miss-;
x->length = x->right - x->left + ;
x->ship = maxShip(*x); sumShip -= shipNum - arr[len].ship - x->ship; // 总容纳战舰数减少的数量等于分段后减少的战舰数量 len++;
} int main() { cin >> n >> k >> a >> m; init(); // 初始化 for(int i = ;i <= m; ++i){
cin >> miss;
updataNode(miss); // 更新段
if(sumShip < k){
cout << i << endl;
return ;
}
}
cout << - << endl;
return ;
}
//written by zhangjiuding.

代码中涉及到的replace是头文件algorithm中的,

replace(a+3,a+10,p,q);

表示的是将a[i](i = [3,9])中的p全部换成q。

上一篇:IOS——触摸事件 视图检测和事件传递


下一篇:django 静态文件