关注
当时自己犯了很蠢的错误,用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
相关推荐
07-18 15:12
华南理工大学 Java 
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 校招阶段,学历VS技术哪个更重要? #
9380次浏览 115人参与
# 顺丰求职进展汇总 #
52832次浏览 283人参与
# 不卡学历的大厂有哪些? #
15813次浏览 113人参与
# 腾讯音乐求职进展汇总 #
96962次浏览 563人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
121178次浏览 1145人参与
# 除了主业以外,你还有哪些其他收入? #
6226次浏览 105人参与
# 实习时,大家都怎么称呼自己的mentor? #
42953次浏览 270人参与
# 摸鱼被leader发现了怎么办 #
60590次浏览 369人参与
# 视觉/交互/设计招聘信息汇总 #
18005次浏览 612人参与
# 社恐入职新公司如何融入团队 #
10813次浏览 62人参与
# 实习如何「偷」产出? #
25113次浏览 317人参与
# 风评不好的公司,你会去吗? #
45117次浏览 320人参与
# 考研可以缓解求职焦虑吗 #
53416次浏览 474人参与
# 职场新人体验 #
14388次浏览 145人参与
# 实习打杂,要跑路吗 #
12426次浏览 157人参与
# 校园里的破防时刻 #
6964次浏览 76人参与
# 金融财经春招备战日记 #
22635次浏览 135人参与
# 求职遇到的搞笑事件 #
121683次浏览 795人参与
# 听到哪句话就代表面试稳了or挂了? #
175898次浏览 1395人参与
# 软开人,秋招你打算投哪些公司呢 #
107609次浏览 976人参与