关注
当时自己犯了很蠢的错误,用Python写一直ac不了,所以搞了两个版本,后来发现都改好了,两个都能AC C++版本: #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX(a,b) ((a) > (b) ? (a) : (b))
using namespace std;
int main(){
int t, res_m, res_f;
cin >> t;
for(int i = 0; i < t; i++){
int n;
res_m = 0;
res_f = 0;
cin >> n;
vector<int> v;
for(int j = 0; j < n; j++){
int x; scanf("%d",&x);
vector<int>::iterator pos_left,pos_right;
pos_left = std::lower_bound(v.begin(), v.end(), x);
pos_right = std::upper_bound(pos_left, v.end(), x);
int lo = pos_left - v.begin();
int hi = pos_right - v.begin();
v.insert(v.begin()+hi, x);
res_f += lo + hi - j;
res_m = MAX(res_m, res_f);
}
cout << res_m << ' ' << res_f << endl;
}
return 0;
} Python 版本: import bisect
T = int(input())
class my_class(object):
__slots__ = ['array', 'res_m', 'res_f']
def __init__(self, lst):
array = []
res_m, res_f = 0, 0
n = len(lst)
for i, x in enumerate(lst):
pos_left = bisect.bisect_left(array, x)
pos_right = bisect.bisect_right(array, x, pos_left)
res_f += pos_left + pos_right - i
res_m = max(res_m, res_f)
array.insert(pos_right, x)
print(res_m, res_f)
for _ in range(T):
n = int(input())
lst = list(map(int, input().split()))
my_class(lst)
查看原帖
点赞 2
相关推荐
点赞 评论 收藏
分享
06-12 17:11
湖南师范大学 算法工程师 点赞 评论 收藏
分享
爱坤ikun:19世纪美国淘金热,挖到金子的人又有多少呢,但是卖淘金子工具的人赚的盆满钵满
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 工作中哪个瞬间让你想离职 #
28524次浏览 200人参与
# 在职场上,你最讨厌什么样的同事 #
16374次浏览 166人参与
# 选了这个offer,你有没有后悔? #
593159次浏览 4029人参与
# 机械人,秋招第一次笔试的企业是哪家? #
41189次浏览 327人参与
# 小米硬件提前批进度交流 #
171166次浏览 1528人参与
# 机械求职避坑tips #
53524次浏览 381人参与
# 哪些公司校招卡第一学历 #
75539次浏览 309人参与
# 担心入职之后被发现很菜怎么办 #
139677次浏览 810人参与
# 入职以后才知道的校招谎言 #
89088次浏览 588人参与
# 职场常用语录大全 #
4199次浏览 32人参与
# Offer比较,你最看重什么? #
192219次浏览 1310人参与
# 华子oc时间线 #
1245117次浏览 6487人参与
# 哪些公司开提前批了? #
30241次浏览 277人参与
# 风评不好的公司,你会去吗? #
66190次浏览 466人参与
# 两会劳动法放大招 #
76728次浏览 692人参与
# 应届生初入职场,求建议 #
230366次浏览 2651人参与
# 实习如何「偷」产出? #
56823次浏览 1398人参与
# 不卡学历的大厂有哪些? #
33281次浏览 254人参与
# 怎么防止在试用期被辞退 #
129226次浏览 927人参与
# 校招阶段,学历VS技术哪个更重要? #
19815次浏览 209人参与