AtCoder Beginner Contest 271赛后总结

3. C - Manga

题目大意：

给出一本书的部分章节（数量n），当我们读取章节时，我们从1开始读并且按照顺序读取，如果某一个章节读取不了，那么就停止。现在我们有一种操作，可以将两个已有的章节换成一个没有的章节，请问最多能读取到第几章节。

题目分析：

我们看到题目以后，我们可以发现我们需要卖掉一些不需要的章节，换取一些可以使读取数增加的章节，那么通过分析我们得到两个规律：

1. 我们最多可以读到n个章节
2. 重复的章节没有用处

章节数大于n的章节和重复的章节就一定可以被卖掉，为了更好的分析，所以我们可以先将这些没用的章节换成有用的章节

for (int i = 1; i <= n; i++)
{
int x;
    cin >> x;
    if (x <= n && box[x] == 0)
        box[x] = 1;
    else
        flag++;
}//统计有多少一定可以卖掉的章节
for (int i = 1; i <= n; i++)
{
    if (box[i] == 0 && flag >= 2)
    {
        box[i] = 1;
        flag -= 2;
    }
}//把卖掉的章节换成新章节

换完我们发现我们还有部分章节是没办法读取的，这是我们就需要卖掉一部分， 由于我们读取章节是从小到大的顺序，所以我们可以从章节数较大的开始卖，注意的是每买一本新的章节以后我们要判断一下这个新的章节是否和下一个章节连在一起。当我们没办法继续卖的时候，答案出来了

for (int i = n; i > ans; i--)
{
	if (box[i] == 1)
	{
		flag++;
		box[i] = 0;
	}//从后往前卖章节，如果卖掉就把box[i]变为0（防止被连起来,而被算进答案）
	if (flag == 2)
	{
		ans++;
		box[ans] = 1;
		flag = 0;
	}//当卖掉两个章节，就可以买新的章节
	while (box[ans + 1] == 1)
	{
		ans++;
		if (ans == n)break;
	}//检查新买的章节有没有连到下一本
}

 全部代码：

#include<stdio.h>
#include<iostream>
using namespace std;
int  box[200000000];
int main()
{
	long long n;
	long long ans = 0;
	long long flag = 0;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		if (x <= n && box[x] == 0)
			box[x] = 1;
		else
			flag++;
	}//统计有多少一定可以卖掉的章节

	for (int i = 1; i <= n; i++)
	{
		if (box[i] == 0 && flag >= 2)
		{
			box[i] = 1;
			flag -= 2;
		}
	}//把卖掉的章节换成新章节

	for (int i = 1; i <= n; i++)
	{
		if (box[i] == 1)
		{
			ans++;
		}
		else
		{
			break;
		}
	}//算出目前可以读取到的章节数

	for (int i = n; i > ans; i--)
	{
		if (box[i] == 1)
		{
			flag++;
			box[i] = 0;
		}//从后往前卖章节，如果卖掉就把box[i]变为0
		if (flag == 2)
		{
			ans++;
			box[ans] = 1;
			flag = 0;
		}
		
		while (box[ans + 1] == 1)
		{
			ans++;
			if (ans == n)break;
		}//检查新买的章节有没有连到下一本
	}

	cout << ans << endl;
	return 0;
}