题解 | #打气球的最大分数#

打气球的最大分数

http://www.nowcoder.com/practice/35119064d0224c35ab1ab612bffee8df

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";

}

全部评论

相关推荐

头像
03-30 21:02
已编辑
武汉大学 Java
ALEX_BLX:虽然说聊天记录不可信,不过这个趋势确实如此但我觉得也要想到一点就是卷后端的人里真正有“料”的人又有多少,我说的这个料都不是说一定要到大佬那种级别,而是就一个正常的水平。即使是现在也有很多人是跟风转码的,2-3个月速成后端技术栈的人数不胜数,但今时不同往日没可能靠速成进大厂了。这种情况就跟考研一样,你能上考场就已经打败一半的人了
点赞 评论 收藏
分享
Wy_m:只要不是能叫的上名的公司 去实习没有任何意义 不如好好沉淀自己
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客企业服务