Maximum Sequence
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1450 Accepted Submission(s): 673
Sample Input
4
8 11 8 5
3 1 4 2
Sample Output
27
Hint
For the first sample:
1. Choose 2 from {bi}, then a_2…a_4 are available for a_5, and you can let a_5=a_2-2=9;
2. Choose 1 from {bi}, then a_1…a_5 are available for a_6, and you can let a_6=a_2-2=9;
Source
题意：给你一个a数组 代表这个数组里的数值 给你一个b数组 代表a数组的位序 在b数组中选一个值 进行奇葩（解释不清楚）操作
8 11 8 5
3 1 4 2 选2 a变成-》8 11 8 5 9 在选1-》 8 11 8 5 9 9 再选3变成8 11 8 5 9 9 5 在选4-》8 11 8 5 9 9 5 4
求增加的数字和最大为多少
题解：其实将b数组排个序 从小到大选取 用一个优先队列维护一下是不是可以取到最大值 因为b数组的值不确定
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdlib> 6 #include<string.h> 7 #include<set> 8 #include<vector> 9 #include<queue> 10 #include<stack> 11 #include<map> 12 #include<cmath> 13 typedef long long ll; 14 typedef unsigned long long LL; 15 using namespace std; 16 const double PI=acos(-1.0); 17 const double eps=0.0000000001; 18 const int N=500000+10; 19 const ll mod=1e9+7; 20 int a[N],b[N]; 21 struct node{ 22 int num; 23 int pos; 24 friend bool operator<(node aa,node bb){ 25 return aa.num<bb.num; 26 } 27 }; 28 priority_queue<node>q; 29 int main(){ 30 int n; 31 while(scanf("%d",&n)!=EOF){ 32 // memset(c,0,sizeof(c)); 33 while(!q.empty())q.pop(); 34 node c; 35 for(int i=1;i<=n;i++){ 36 scanf("%d",&a[i]); 37 c.num=a[i]-i; 38 c.pos=i; 39 q.push(c); 40 } 41 //cout<<q.top().num<<endl; 42 for(int i=1;i<=n;i++)scanf("%d",&b[i]); 43 sort(b+1,b+1+n); 44 ll ans=0; 45 node t; 46 int tt=n+1; 47 for(int i=1;i<=n;i++){ 48 while(b[i]>q.top().pos)q.pop(); 49 if(q.empty()==1)break; 50 c=q.top(); 51 ans=(ans+c.num)%mod; 52 t.num=c.num-tt; 53 t.pos=tt; 54 q.push(t); 55 tt++; 56 //cout<<c.num<<endl; 57 } 58 ans%=mod; 59 printf("%I64d ",ans); 60 } 61 }