0816 京东笔试答案-减小逆序对-跳水运动
题目一：减小逆序对
题目简介：减少逆序对,给t组测试数据,每组给一个n,给一个序列A：a1,a2,a3...an;可以做的操作是在A序列的[L,R]范围上+1，且该操作只能做一次,使用该操作最多能让逆序对减少多少。
思路：首先给[L,R]范围上+1使得逆序对减少,那么带来的影响是会让[0,L-1]上的逆序对减少,但是也可能会让[R+1,N]范围上的逆序对增多，所以对于任意的[L,R] -->[L,N]一定是优于或者等于[L,R]的答案的,因为即没有影响正向影响，同时也取消了负面影响.
代码实现思路:dp[i] = 以i当成L的情况下带来的影响，那么dp[i] = {[0,i-1]所有值等于a[i] + 1的个数} + dp[i+1] -
{[i+1,n]所有值等于a[i]-1 的值}
也就是说在计算{[0,i-1]所有值等于a[i] + 1的个数}的时候所有满足条件的j在dp[j]处也会-1,因为随着i倒序向前增长,i的范围扩大
的同时,本来给当前i造成贡献的位置j,在dp[j]的时候因为+1了所以要减掉在i的时候造成的贡献。
例如 在dp[5] 的时候应该等于{前面 [0,4] 范围中所有值等于a[5] + 1的数的个数} + dp[6] - {[6,N]中所有值等于a[5] - 1}的数就是dp[5]的答案。
但是后面这一步是不用减的因为在前面的某一步中例如a[5]的值刚好等于a[i]+1那么在操作dp[i]的时候会顺便把dp[5]--，就是这个意思。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],t,n,dp[N];
vector<int> cnt[N];
int main(){
cin>>t;
while(t--){
cin>>n,memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]].clear(),cnt[a[i]+1].clear();
for(int i=1;i<=n;i++)cnt[a[i]].push_back(i);
for(int i=n;i>0;i--){
dp[i]+=dp[i+1];
for(auto j:cnt[a[i]+1]) if(j<i) dp[j]--,dp[i]++;
}
int ans = 0;
for(int i=1;i<=n;i++)ans = max(ans,dp[i]);
cout<<ans<<endl;
}
}
题目二：跳水运动
这题就是滑动窗口+前缀和就不说了。
#秋招白月光##笔试#
阿里巴巴一面429人在聊
投递京东等公司10个岗位