题解 | #用栈来求解汉诺塔问题#

用栈来求解汉诺塔问题

http://www.nowcoder.com/practice/1a2f618b3433487295657b3414f4e7c4

include

include

using namespace std;
typedef long long ll;

const int MAXN = 210 * 2;
const int SHIFT = 102;
ll bit[MAXN];

void bitAdd(int x, int v) {
while (x < MAXN) {
bit[x] += v;
x += (x & (-x));
}
}

ll bitSum(int x) {
ll sum = 0;
while (x > 0) {
sum += bit[x];
x -= (x & (-x));
}
return sum;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

int N; cin >> N;
ll ans = 0;
memset(bit, 0, sizeof(bit));
for (int i = 0; i < N; ++i) {
    int t; cin >> t; t += SHIFT;
    ans += bitSum(t);
    bitAdd(t, t - SHIFT);
}
cout << ans << "\n";

}

全部评论

相关推荐

12-15 14:16
门头沟学院 Java
回家当保安:发offer的时候会背调学信网,最好不要这样。 “27届 ”和“28届以下 ”公司招聘的预期是不一样的。
实习简历求拷打
点赞 评论 收藏
分享
12-22 16:31
已编辑
桂林电子科技大学 Python
很奥的前端仔:如果你接了offer 临时又说不去 hr确实要多做一些工作。 当然如果是接offer之前当我没说
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务