【Codeforces 567D】One-Dimensional Battle Ships

【链接】我是链接,点我呀:)

【题意】

长度为n的一个序列,其中有一些部分可能是空的,一些部分是长度为a的物品的一部分

(总共有k个长度为a的物品,一个放在位置i长度为a的物品会占据i,i+1,....i+a-1这a个格子

(物品之间必须要有至少一个空格,不能相邻

现在有一个人猜了m个不同的位置

你每次都说那个位置不是物品的一部分。(骗他)

那么请问最少在第几次你会露馅?(知道你在骗他)

【题解】

对于一个连续的空白的区间[l,r],设其长度为len=r-l+1
那么这个空白区间最多能放下(len+1)/(a+1)个物品
(注意每个物品之间至少要有一个空格,所以每个物品理论上占据了a+1个空间
(但是最后一个物品它最后面可以不用有空格,因此我们可以多给它一个"虚拟"空间,覆盖到这种情况
可以这样做,我们按顺序加入那个人猜的断点
将包含这个断点的区间(一开始只有[1,n+1),注意一定要用左闭右开区间,不然类似[x,x]这样的区间不好表示
分成[l,x-1]和[x+1,r]
并且减去[l,r]能放下的物品数
然后改为增加两个子区间能放下的物品数
直到能放下的物品数量小于k为止
(用一个一个的点来表示区间,注意这个区间里面的区间都是左闭右开区间)
(在分成两个子区间之后,我们会在集合中加入x和x+1,理论上我们还能通过查找x找到[x,x+1)这个区间,但是这个区间其实是不存在的了)
(插入的x仅仅是为了给[l,x)这个区间服务的,因为不会重复猜测所以没影响

【代码】

import java.io.*;

import java.util.*;

public class Main {

    static InputReader in;

    static PrintWriter out;

    public static void main(String[] args) throws IOException{

        //InputStream ins = new FileInputStream("E:\\rush.txt");

        InputStream ins = System.in;

        in = new InputReader(ins);

        out = new PrintWriter(System.out);

        //code start from here

        new Task().solve(in, out);

        out.close();

    }

    static int N = 50000;

    static class Task{

        int n,k,a;

        int m;

        TreeSet myset = new TreeSet();

        int _get(int len) {

        	return (len+1)/(a+1);

        }

        public void solve(InputReader in,PrintWriter out) {

        	n = in.nextInt();k = in.nextInt();a = in.nextInt();

        	m = in.nextInt();

        	myset.add(1);myset.add(n+1);

        	int ans = _get(n);

        	for (int i = 1; i <= m;i++) {

        		int x;

        		x = in.nextInt();

        		int r= (int)myset.higher(x);

        		int l = (int)myset.floor(x);

        		ans = ans-_get(r-l);

        		//l..x-1

        		if (l<=x-1) {

        			myset.add(x);

        			ans = ans + _get(x-1-l+1);

        		}

        		//x+1..r-1

        		if (x+1<=r-1) {

        			myset.add(x+1);

        			ans = ans + _get(r-1-(x+1)+1);

        		}

        		if (ans<k) {

        			out.println(i);

        			return;

        		}

        	}

        	out.println(-1);

        }

    }

    static class InputReader{

        public BufferedReader br;

        public StringTokenizer tokenizer;

        public InputReader(InputStream ins) {

            br = new BufferedReader(new InputStreamReader(ins));

            tokenizer = null;

        }

        public String next(){

            while (tokenizer==null || !tokenizer.hasMoreTokens()) {

                try {

                tokenizer = new StringTokenizer(br.readLine());

                }catch(IOException e) {

                    throw new RuntimeException(e);

                }

            }

            return tokenizer.nextToken();

        }

        public int nextInt() {

            return Integer.parseInt(next());

        }

    }

}

巴特西

【Codeforces 567D】One-Dimensional Battle Ships

最新文章

热门文章