题目描述
一共有 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;
}
