基本情况
AB秒了，C卡了一个半小时，+7出来了。
C. Grouping Increases
动规思路
最初的想法是二分加动规求lis 然后状态记录后再记录剩下的那个序列的贡献。
void close_sync()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), low(n + 1), pos(n + 1), vis(n + 1);
bool ok = true;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i >= 2 && a[i] != a[i - 1]) ok = false;
}
low[1] = a[1];
int len = 1;
pos[1] = len;
for (int i = 2; i <= n; i++)
{
if (a[i] >= low[len])
{
low[++len] = a[i];
pos[i] = len;
}
else
{
int index = lower_bound(low.begin() + 1, low.begin() + 1 + len, a[i]) - low.begin();
low[index] = a[i];
pos[i] = index;
}
}
int maxx = 0x7fffffff, tem = len;
for (int i = n; i >= 1; i--)
{
if (tem == 0)
break;
vis[pos[i]] = true;
if (pos[i] == tem && maxx >= a[i])
{
tem--;
maxx = a[i];
}
}
int sum = 0;
vector<int> ans;
for (int i = 1; i <= n; i++) if(!vis[i]) ans.push_back(a[i]);
if (ans.empty())
{
if (ok) cout << "0\n";
else cout << (n + 1) / 2 << '\n';
return ;
}
for (int i = 0; i < ans.size(); i++)
{
if (ans[i] < ans[i + 1]) sum++;
}
cout << sum << '\n';
return ;
}
但是这是错的。
比如对于
9 7 6 5 1 1 1 1 4 6 3 5 2 4
求 lis 的话显然是
9 7 6 5 1 1 1 1
然后剩下的是
4 6 3 5 2 4
这样贡献就是 \(3\)。
然而显然可以取 9 7 6 5 4 3 2 和 1 1 1 1 6 5 4
这样贡献仅有 \(1\)。
贪心思路
那就只好贪心了。
对于每个数，要么去 \(a\)，要么去 \(b\)。
最显然的，肯定是跟这两个队列的末尾比较，如果刚好一个可以放一个不能放，那就放可以放的。
但难点在想到两个可以放、两个不能放的情况。
- 对于两个都可以放，放入队尾较小的那一队
- 因为这样可以提高容错，让队尾大的留下来。
- 对于两个都不可以放，也放入队尾较小的一队。
- 这样可以保留相对来说大的队尾。
这个思路想到之后就好实现了。
void solve()
{
int n;
cin >> n;
queue<int> a, b;
int x, sum = 0;
a.push(1e9), b.push(1e9);
for (int i = 1; i <= n; i++)
{
cin >> x;
bool f1 = x <= a.back(), f2 = x <= b.back();
if (f1 && f2)
{
if (a.back() <= b.back()) a.push(x);
else b.push(x);
}
else if ((!f1) && (!f2))
{
if (a.back() <= b.back()) a.push(x);
else b.push(x);
sum++;
}
else if (f1) a.push(x);
else if (f2) b.push(x);
}
cout << sum << '\n';
}