codeforces 567D.One-Dimensional Battle Ships 解题报告

时间:2022-10-29 14:52:15

题目链接:http://codeforces.com/problemset/problem/567/D

题目意思:给出 1 * n 的 field,编号从左至右依次为 1,2,...,n。问射 m 枪之后(第 i 次射中编号 xi,则 xi 这一点是不能放置船只的!),能不能将 k 只 1 * a 的小船放到这些没有经过被射中编号的 field 中 。由于Alice 每次 shoot 的时候都会说 miss 的,即没有打中,你需要判断第几次shoot 使得整个field 不能放置 k 只 小船,如果都能放,最终输出 - 1.

  首先,外国人的题解真是好严谨,又好体~~~

codeforces  567D.One-Dimensional Battle Ships  解题报告

  有几点需要解释下。事实上这几点也困惑了我好久 0.0

  (1)一开始整个区间 (n+1)/(a+1) 可能好多人还是不太明白。那么列条方程帮助理解吧。假设在[1, n] 中最多可以放置 x 只船,可以列出 x * a + (x - 1) = n,于是经若干合并同类项,就可以得到 x =  (n+1)/(a+1)。或者可以按题解者那样理解,由于最大放船数肯定是从最边边开始放的啦,然后间隔一个shoot之后随之放入另一只船。。。很容易知道,每只船占的空间至少为a+1(最尾那只可能不止又或者是a(可喜可贺啊)),那么我们可以虚拟多一个编号为 n+1 的 field。所以整个长度就为 (n+1)/ (a+1)了,很神奇哇~

  (2)(r-l+2)/(a+1) 是啥来的?!如果理解了第一点就很容易明白了。我们shoot完之后,这个 shoot 将空间一分为二了,选定的空间我们用集合set 的 upper_bound来找,返回的是 r ,前一个就是  l 。r-l+1很容易理解(不理解可以私聊我),再+1 就是虚拟的那个field。第(1)点已经说了,紧挨着边放置是最优解的条件!最后记得把shoot这个编号放入下一轮备选空间上。

  (3)空间中为什么要减完再加。因为有个shoot将空间一分为二嘛~~这个时候可以放置的船已经不是原来的[l, r] 这么多了。而是被分开的左区间[l, x-1] 和 [x+1, r] 之和这么多。

  

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std; set<int> s; int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE int m, n, a, k, x;
while (scanf("%d%d%d", &n, &k, &a) != EOF) {
scanf("%d", &m);
s.clear();
s.insert(), s.insert(n+); // 实现虚拟长度的小技巧
int sum = (n+) / (a+);
int ans = -, f = ;
for (int i = ; i <= m; i++) {
scanf("%d", &x);
set<int>::iterator it = s.upper_bound(x);
int r = *it;
int l = *(--it);
sum = sum - (r-l)/(a+) +(x-l)/(a+) + (r-x)/(a+); if (sum < k && !f) {
ans = i;
f = ;
}
s.insert(x);
}
printf("%d\n", ans);
}
return ;
}

  

  

codeforces 567D.One-Dimensional Battle Ships 解题报告的更多相关文章

  1. Codeforces 567D:One-Dimensional Battle Ships(二分)

    time limit per test : 1 second memory limit per test : 256 megabytes input : standard input output : ...

  2. 【Codeforces 567D】One-Dimensional Battle Ships

    [链接] 我是链接,点我呀:) [题意] 长度为n的一个序列,其中有一些部分可能是空的,一些部分是长度为a的物品的一部分 (总共有k个长度为a的物品,一个放在位置i长度为a的物品会占据i,i+1,.. ...

  3. codeforces C1&period; The Great Julya Calendar 解题报告

    题目链接:http://codeforces.com/problemset/problem/331/C1 这是第一次参加codeforces比赛(ABBYY Cup 3.0 - Finals (onl ...

  4. codeforces B&period; Eugeny and Play List 解题报告

    题目链接:http://codeforces.com/problemset/problem/302/B 题目意思:给出两个整数n和m,接下来n行给出n首歌分别的奏唱时间和听的次数,紧跟着给出m个时刻, ...

  5. codeforces 433C&period; Ryouko&&num;39&semi;s Memory Note 解题报告

    题目链接:http://codeforces.com/problemset/problem/433/C 题目意思:一本书有 n 页,每页的编号依次从 1 到 n 编排.如果从页 x 翻到页 y,那么| ...

  6. codeforces 556B&period; Case of Fake Numbers 解题报告

    题目链接:http://codeforces.com/problemset/problem/556/B 题目意思:给出 n 个齿轮,每个齿轮有 n 个 teeth,逆时针排列,编号为0 ~ n-1.每 ...

  7. codeforces 510B&period; Fox And Two Dots 解题报告

    题目链接:http://codeforces.com/problemset/problem/510/B 题目意思:给出 n 行 m 列只有大写字母组成的字符串.问具有相同字母的能否组成一个环. 很容易 ...

  8. codeforces 505A&period; Mr&period; Kitayuta&&num;39&semi;s Gift 解题报告

    题目链接:http://codeforces.com/problemset/problem/505/A 题目意思:给出一个长度不大于10的小写英文字符串 s,问是否能通过在字符串的某个位置插入一个字母 ...

  9. codeforces 499A&period;Inna and Pink Pony 解题报告

    题目链接:http://codeforces.com/problemset/problem/499/A 题目意思:有两种按钮:1.如果当前观看的时间是 t,player 可以自动处理下一分钟,姑且理解 ...

随机推荐

  1. mysql5&period;6&period;23免安装配置

    1.官网下载,并解压 2.环境变量,path下,追加mysql的bin路径D:\Program Files\mysql\bin; 3.mysql目录下的my-default.ini重命名为my.ini ...

  2. SharePoint 2016 Beta 2 安装体验

    博客地址:http://blog.csdn.net/FoxDave 最近忙碌了一段时间,2016正式版快要发布了,想尽快熟悉熟悉.2016不再提供免费版Foundation的支持,只有Server版本 ...

  3. linux source与 &period; 命令

    source命令用法:source FileName作用:在当前bash环境下读取并执行FileName中的命令.注:该命令通常用命令“.”来替代.如:source .bash_rc 与 . .bas ...

  4. JS 原型继承的几种方法

    <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...

  5. SubsetsTotal Accepted&colon;49746Total Submissions&colon;176257My Submissions

    Subsets Total Accepted: 49746 Total Submissions: 176257My Submissions Given a set of distinct intege ...

  6. WinForm C&num;全局错误捕捉处理【整理】

    static class Program { /// <summary> /// 应用程序的主入口点. /// </summary> [STAThread] static vo ...

  7. 每个QWidget都有contentsMargins函数,善用QMargins

    m_pSearchLineEdit = new QLineEdit(); QPushButton *pSearchButton = new QPushButton(this); pSearchButt ...

  8. Ext4报错Uncaught Ext&period;Loader is not enabled

    提示: Uncaught Ext.Loader is not enabled, so dependencies cannot be resolved dynamically. Missing requ ...

  9. JAVA Static方法与单例模式的理解

    近期用sonar測评代码质量的时候,发现一个问题,project中一些util类,曾经写的static方法都提示最好用单例的方式进行改正. 为此,我细致想了想,发现还是非常有道理的.这里谈谈我个人对s ...

  10. 24&period; leetcode 409&period; Longest Palindrome

    409. Longest Palindrome Given a string which consists of lowercase or uppercase letters, find the le ...