菜鸡的解法(使用STL,实现更简单)
题目描述
详情见题目
样例
详情见题目~
神牛手写merge,本人既菜又懒,用STL中的归并。本以为这样疯狂使用vector会T的。(tourist祝福hhhh)
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<assert.h>
#define int long long
using namespace std;
int N, M, T;
inline int check(vector<int> v){
if(v.size() < 2) return 0;
int m = min(M, (int)(v.size() >> 1));
int sum = 0;
for(int i=0; i<m; i++){
sum += ( v[i] - v[v.size() - i - 1] )*( v[i] - v[v.size() - i - 1] );
}
return sum;
}
int solve(){
vector<int> v(N);
for(int i=0; i<N; i++){
cin >> v[i];
}
int cnt = 0;
int L = 0, R = 0;
while(R < N){
int p = 1;
vector<int> save;
while(p){
if(R + p < N + 1){
vector<int> tmp(p);
for(int i=R; i<R+p; i++){
assert(i < N);
tmp[i - R] = v[i];
}
sort(tmp.begin(), tmp.end());
vector<int> tmp1;
tmp1.resize(tmp.size() + save.size());
merge(tmp.begin(), tmp.end(), save.begin(), save.end(), tmp1.begin());
if(check(tmp1) <= T){
R += p;
p <<= 1;
save = tmp1;
}else
p >>= 1;
}else
p >>= 1;
}
L = R;
cnt ++;
}
return cnt;
}
signed main(void){
int K;
cin >> K;
while(K--){
cin >> N >> M >> T;
cout << solve() << endl;
}
return 0;
}
时限10sqwq
emm…强