首页 > 代码库 > 股票交易（洛谷U6084)
股票交易（洛谷U6084)
题目背景
kkk最近迷上了炒股。
题目描述
kkk炒了N天股，第i天的股价为a[i]元。kkk希望股票每天都上涨1元钱，但是操盘手lzn并不想让kkk赚很多钱导致他亏本，于是a[i]相对a[i-1]就有了起伏。
如果以某一天的股价a[x]为基准，第x+k(x+k<=N)天的股价a[x+k]比希望的低，kkk就认为lzn坑了他一次。kkk要知道lzn总共坑了他多少次，以便找lzn算账。
输入输出格式
输入格式：
第一行一个整数N
接下来N个整数a[i]
输出格式：
总共坑了kkk多少次，对23333取模
输入输出样例
输入样例#1：
3
1 3 3
输出样例#1：
1
说明
样例解释：以第2天为基准，第3天的股价比希望的低。
1<=N<=100000
1<=a[i]<=2000
温馨提示：如果暴力得了0分，可以把大于号(小于号)改成小于号(大于号)试试。
/* 跟第一题很像，本题要求i>j&&a[i]-a[j]<(i-j)的个数，我们可以现将每个a[i]都减去i，然后再求逆序对。 */ #include<cstdio> #include<cstring> #include<iostream> #define N 100010 #define mod 23333 using namespace std; int a[N],b[N],n;int ans; void merge_sort(int s,int t){ if(s>=t)return; int mid=(s+t)>>1; merge_sort(s,mid); merge_sort(mid+1,t); int i=s,j=mid+1,k=s; while(i<=mid&&j<=t){ if(a[j]>a[i]){ b[k]=a[j]; j++;k++;ans+=mid-i+1;ans%=mod; } else { b[k]=a[i]; i++;k++; } } while(i<=mid){b[k]=a[i];i++;k++;} while(j<=t){b[k]=a[j];j++;k++;} for(int l=s;l<=t;l++)a[l]=b[l]; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=i; merge_sort(1,n); printf("%d",ans); return 0; }
股票交易（洛谷U6084)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。