![在这里插入图片描述](https://img-blog.csdnimg.cn/2acfa3455a424d9a9f39bac726dc1936.png) ![在这里插入图片描述](https://img-blog.csdnimg.cn/4f480197976b4a9ebeb73aec842d255a.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/9253779635954c74855a8e5117903110.png) ![在这里插入图片描述](https://img-blog.csdnimg.cn/130bf40145a0461392e1cf82d0c6285f.png)
题目描述
一共有 n 个语句。若语句 i 向语句 j 调用(j < i ),则这里两个语句之间必须 至少间隔三个语句(其中包括了 空语句 和 非空语句),否则会出现问题。
题目输出给定语句调用表。
你要插入最少数量的空白语句,来满足所有语句调用没有问题。
题目可能较难理解,我们根据样例进行进一步解释:
样例
输入:
4 //第一行包括一个整数 n ,表示 程序原有语句总数
0 0 0
1 0 0
0 1 0
0 0 0
// 上面 n 行,第 i 行描述了第 i 条程序语句,每行有 3 个数字。
第 i 行第 j 个数字 a[i, j](为 0 或 1),表示 第 i 句 向 第 i ? j 句 调用时是否出现了问题,为 1 表示出现了问题
(即第 i ? j 句写入了某一寄存器,而第 i 句又要读取同一寄存器,发生了矛盾),为 0 表示没有出现问题。
输入表示发生调用问题的语句对有:
第二句 非法调用 第一句、 第三句 非法调用 第一句。
输出:
一种插入三个空语句的 最优策略 为:
原第一句、空语句、空语句、空语句、原第二句、原第三句、原第四句。
即 至少加入 3 个空语句,输出为 3
3
算法
(树状数组 + 贪心)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
根据题意,我们需要求得 总插入空格的最小值。
我们用 变量 res 存放 当前插入的空格数,用 树状数组 s 方便 动态维护 空语句前缀和,ask(x) 表示 语句 1 到 语句 x 之间 空语句总数,若求 区间 [l, r] 中空语句数量,即为:ask(r) - ask(l - 1)
输入 语句调用表,当输入的数字 a[i][j] 为 1 的时候,表示 语句 i 调用 语句 i - j 出现了问题,
这时候,我们先计算 两个语句之间(不包括这两个语句)有多少个 非空语句,显然为:t1 = i - (i - j) - 1 ,如:语句 3 和 语句 1 之间 非空语句数为 1 (语句 2 )
后计算 两个语句之间 当前 有多少个 空语句:t2 = ask(i) - ask(i-j-1);
两语句间的 总语句数 为 sum = t1 + t2 ,
如果 sum < 3 ,显然会造成 调用矛盾,因此这时 当前插入的空格数 res 应当 加上 3 - sum 个 空语句,才能使两语句间的语句数(包括 空语句 和 非空语句)恰好等于 3 (由题意此时 恰好两语句无矛盾),
注意,树状数组 s 是 实时动态维护序列前缀和 的,我们需要在 当前语句 i 和 上一个语句 i - 1 ,之间 增加 3 - sum 个空语句,直接 执行add(i - 1, 3 - sum) 即可,
不过为什么要在 当前语句 i 和 上一个语句 i - 1 之间 增加 空语句 呢?
这其实是基于 贪心 的思想:我们要在当前语句之前,且距离它尽可能近的地方 插入空语句,可见最优插入位置为 当前语句 i 和 上一个语句 i - 1 之间。
时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 110;
bool g[N][N];
int s[N];
inline int lowbit(int x) {return x & (-x);}
int ask(int x)//查询前缀空语句和
{
int ans = 0;
while(x) {ans += s[x], x -= lowbit(x);}
return ans;
}
void add(int x, int y)//在语句 x 之后插入 y 个空语句
{
for(; x<=n; x+=lowbit(x)) s[x] += y;
}
int main()
{
cin>>n;
int res = 0;//已经插入的空格
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=3; ++j)
{
cin>>g[i][j];
if(g[i][j])
{
int t1 = i - (i - j) - 1;//语句 i 和 语句 i-j 之间的 非空语句 个数
int t2 = ask(i) - ask(i-j-1);//两个语句之间 当前 有多少个 空语句
int sum = t1 + t2;//两语句间的总语句数
if(sum < 3)
{
res += 3 - sum;
add(i - 1, 3 - sum);
}
}
}
}
cout<<res<<endl;
return 0;
}
|