本文共 4486 字，大约阅读时间需要 14 分钟。
预处理：a_i -= i ，易证明从最小的b开始选每次选最大的一定可以使结果最大。 证明思路：如果条件改为a_i<=max{a_j-j|b_k<=j<=n}，那么b的顺序与最后的结果无关。条件改回来后，由于每次要计算一个数的最大值时都有a_(n+1)...a_(i-1)在范围中，所以每次只需让a_i - i尽可能大，那么就把大的数尽早用上，每次一定考虑尽量多的数字，这样取得的数字就尽可能的大。 所以说每次就是求区间最值，加在答案上。由于贪心的思路，每次要求的区间的下界是单调不降的，故可以用单调队列优化到O(n)的复杂度。 由于1 ≤ b_i ≤ n，对b排序可以用哈希排序（桶排序）完成。 进一步观察，可以发现这样贪心时 a_(n+1)...a_i 其实是单调不增的，所以并不需要每次求区间最值了，选第一个数时就选最大的，后面的选择顺序与最终结果无关了。
#include #include #include #include #include #include #include #include
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <list>
#include <bitset>
#include <stack>
#include <stdlib.h>
#define lowbit(x) (x&-x)
#define e exp(1.0)
//ios::sync_with_stdio(false);
// auto start = clock();
// cout << (clock() - start) / (double)CLOCKS_PER_SEC;
typedef long long ll;
typedef long long LL;
using namespace std;
const int maxn=250005;
const int mod=1e9+7;
int n;
struct node
{
int id,value;
};
int a[maxn];
vector<int>b;
int num[maxn];
deque<node>que;
ll ans;
int main()
{
while(cin>>n)
{
ans=0;
memset(num,0,sizeof(num));
memset(a,0,sizeof(a));
que.clear();
b.clear();
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int x;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
num[x]++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=num[i];j++)
b.push_back(i);
for(int i=1;i<=n;i++)
{
while(!que.empty() && que.back().value<=a[i]-i)
que.pop_back();
que.push_back({i,a[i]-i});
}
for(int i=1;i<=n;i++)
{
while(que.front().id<b[i-1])
que.pop_front();
int t=que.front().value;
ans=(ans+t)%mod;
t=max(t-n-i,0);
while(que.back().value<=t)
que.pop_back();
que.push_back({n+i,t});
}
cout<<ans<<endl;
}
return 0;
}
另解：
//优先队列
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<string>
- #include<algorithm>
- #include<queue>
- #include<stack>
- #include<set>
- #include<map>
- #include<vector>
- using namespace std;
- typedef long long ll;
- const int maxn = 250010;
- const int mod = 1e9+7;
- int n;
- int a[maxn];
- int b[maxn];
- struct Node{
- int val;
- int id;
- friend bool operator < ( const Node &a, const Node &b)
- {
- if( a.val != b.val)
- return a.val < b.val;
- return a.id > b.id;
- }
- };
- priority_queue<Node> q;
-
- int main()
- {
- while( ~scanf("%d",&n))
- {
- while( !q.empty())
- q.pop();
- Node tmp;
- for( int i = 1; i <= n; i++)
- {
- scanf("%d",&a[i]);
- tmp.id = i;
- tmp.val = a[i]-i;
- q.push(tmp);
- }
- for( int i = 1; i <= n; i++)
- scanf("%d",&b[i]);
- sort(b+1,b+1+n);
- ll ans = 0;
- int p = 1;
- while( p <= n)
- {
- tmp = q.top();
- while( b[p] > tmp.id)
- {
- q.pop();
- tmp = q.top();
- }
- ans=(ans+tmp.val)%mod;
- tmp.val -= (n+p);
- tmp.id = n+p;
- q.push(tmp);
- p++;
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
//单调队列
- #include<cstdio>
- #include<cmath>
- #include<cstring>
- #include<algorithm>
- #include<iostream>
-
- using namespace std;
- #define LL long long
- const int mod = 1e9+7;
- const int maxn = 250010;
- int n;
- int a[maxn];
- int b[maxn];
- struct Node{
- int id;
- int val;
- };
- Node q[maxn<<1];
-
- int main()
- {
- while( ~scanf("%d",&n))
- {
- int head = 0;
- int tail = 0;
- for( int i = 1; i <= n; i++)
- {
- scanf("%d",&a[i]);
- if( tail == 0)
- {
- q[tail].id = i;
- q[tail++].val = a[i]-i;
- }
- else
- {
- while( head < tail && a[i]-i >= q[tail-1].val)
- tail--;
- q[tail].id = i;
- q[tail++].val = a[i]-i;
- }
- }
- for( int i = 1; i <= n; i++)
- scanf("%d",&b[i]);
- sort(b+1,b+1+n);
-
- int p = 1;
- Node tmp;
- LL ans = 0;
- while( p <= n)
- {
- while( b[p] > q[head].id)
- head++;
- ans = (ans+q[head].val)%mod;
- tmp.id = p+n;
- tmp.val = q[head].val-(n+p);
- while( head < tail && tmp.val >= q[tail-1].val)
- tail--;
- q[tail++] = tmp;
- p++;
- }
- printf("%lld\n",ans);
-
- }
-
- return 0;
- }
转载地址：http://xlali.baihongyu.com/