双结构调度器

题意：维护一个栈和一个队列，实现加入数据、弹出数据、访问数据和。

直接实现栈和队列的代码后模拟操作，使用数组形式的实现还是STL皆可。特殊的，当弹出/访问栈顶和队列，但对应数据结构为空时，不加特判会产生错误，此时需要特殊判断

//数组形式实现
#include<iostream>
using namespace std;
const int N=1e6+10;
int top;
int sta[N];
int front,back;
int que[N];
void push_stack(int x){
    top++;
    sta[top]=x;
}
void push_queue(int x){
    back++;
    que[back]=x;
}
void pop_stack(){
    if(top)top--;
}
void pop_queue(){
    if(front<=back)front++;
}
int query_stack(){
    if(top)return sta[top];
    else return 0;
}
int query_queue(){
    if(front>back)return 0;
    else return que[front];
}
void move_sq(){
    if(top){
        int x=query_stack();
        pop_stack();
        push_queue(x);
    }
}
void move_qs(){
    if(front<=back){
        int x=query_queue();
        pop_queue();
        push_stack(x);
    }
}
int main(){
    int n;
    cin>>n;
    front=1;
    for(int i=1;i<=n;i++){
        string op;cin>>op;
        if(op=="PUSH"){
            int x;cin>>x;
            push_stack(x);
        }
        if(op=="ENQUEUE"){
            int x;cin>>x;
            push_queue(x);
        }
        if(op=="MOVE_SQ"){
            move_sq();
        }
        if(op=="MOVE_QS"){
            move_qs();
        }
        if(op=="POP_S"){
            pop_stack();
        }
        if(op=="POP_Q"){
            pop_queue();
        }
        if(op=="QUERY"){
            cout<<query_stack()+query_queue()<<"\n";
        }
    }
}

//STL形式实现
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
const int N=1e6+10;
int main(){
    int n;
    cin>>n;
    stack<int>st;
    queue<int>que;
    for(int i=1;i<=n;i++){
        string op;cin>>op;
        if(op=="PUSH"){
            int x;cin>>x;
            st.push(x);
        }
        if(op=="ENQUEUE"){
            int x;cin>>x;
            que.push(x);
        }
        if(op=="MOVE_SQ"){
            if(st.size()){
                int x=st.top();
                st.pop();
                que.push(x);
            }
        }
        if(op=="MOVE_QS"){
            if(que.size()){
                int x=que.front();
                que.pop();
                st.push(x);
            }
        }
        if(op=="POP_S"){
            if(st.size())st.pop();
        }
        if(op=="POP_Q"){
            if(que.size())que.pop();
        }
        if(op=="QUERY"){
            int x=0,y=0;
            if(st.size())x=st.top();
            if(que.size())y=que.front();
            cout<<x+y<<"\n";
        }
    }
}

颜色区间统计

题意：给定一个只包含数字 $1$ 和 $2$ 的数组，求有多少区间满足，出现个数多的数字大于等于 $A$ ,出现次数少的数字个数大于等于 $B$。

题解：对于一个区间，假设我们固定左端点，随着右端点的向后移动，区间数字个数只会增加。所以当区间 $[l,r]$ 满足条件时，区间 $[l,r+1]$ 一定也满足条件。所以我们可以固定住端点 $l$ ，用二分查找找到第一个满足条件的端点 $r$。快速求出求安某一个数字出现次数，可以使用前缀和数组辅助计算。时间复杂度$O(nlogn)$ 更进一步推导，令 $r$ ，为端点 $l$ 满足条件的第一个右端点 ，令 $r'$ 为端点 $l'$ 满足条件的第一个右端点 ，若 $l<l'$ ,则 $r \leq r'$。这是满足双指针算法的性质，我们可以使用双指针算法解决该问题。时间复杂度$O(n)$。

//二分写法
#include<iostream>
using namespace std;
using ll=long long ;
const int N=2e5+10;
int n,A,B;
int a[N],sum1[N],sum2[N];
ll ans;
int main(){
    cin>>n>>A>>B;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1)sum1[i]=1;
        else sum2[i]=1;
        sum1[i]+=sum1[i-1];
        sum2[i]+=sum2[i-1];
    }
    for(int i=1;i<=n;i++){//枚举左端点
        int l=i,r=n,res=n+1;//res记录第一个满足条件的右端点下标
        while(l<=r){//二分
            int mid=(l+r)/2;
            //利用前缀和数字辅助计算区间1和2数量
            int s1=sum1[mid]-sum1[l-1];
            int s2=sum2[mid]-sum2[l-1];
            if(min(s1,s2)<B||max(s1,s2)<A){//如果不满足条件，数字需要更多
                l=mid+1;
            }
            else{//满足条件就记录答案
                res=mid;
                r=mid-1;
            }
        }
        ans+=n+1-res;
    }
    cout<<ans<<"\n";
}

//双指针写法
#include<iostream>
using namespace std;
using ll=long long ;
const int N=2e5+10;
int n,A,B;
int a[N];
ll ans;
int main(){
    cin>>n>>A>>B;
    for(int i=1;i<=n;i++){
        cin>>a[i]; 
    }
    for(int l=1,r=0,sum1=0,sum2=0;l<=n;l++){
        while(r<n&&(min(sum1,sum2)<B||max(sum1,sum2)<A)){
            r++;
            if(a[r]==1)sum1++;
            else sum2++;
        }
        if(min(sum1,sum2)>=B&&max(sum1,sum2)>=A){
            ans+=n-r+1;
        }
        if(a[l]==1)sum1--;
        else sum2--;
    }
    cout<<ans<<"\n";
}

任务排序

题意：每个任务可以获得 $a_i$ 的收益，对于任意一对任务 $(i,j) , i < j$ ,会使得总收益减少 $\frac{x_i}{t_i * t_j}$ ，任意安排任务顺序使得最终总收益最大。

题解：由于每个任务实际获得收益和顺序无关，要使得总收益最大，只需要使得减少的收益尽可能少。 任意一对任务都可能使得总收益减少，考虑任意一对任务 $(i,j)$。任务 $i$ 在前减少的收益为 $\frac{x_i}{t_i * t_j}$，任务 $j$ 在前减少的收益为 $\frac{x_j}{t_i * t_j}$，要使得减少收益尽可能小，则需要将 $x$ 值更小的任务放在前面。 所以使用贪心算法安排任务顺序，按照 $x$ 从小到大完成任务。 安排任务顺序之后，如何快速计算所有任务减少的收益？考虑固定住任务 $j$。所有小于 $j$ 的任务对任务$j$ 的影响之和为$\sum_{i=1}^{j-1}\frac{x_i}{t_i * t_j}$ ，提取 $\frac{1}{t_j}$, 式子变为$\frac{1}{t_j} * \sum_{i=1}^{j-1}\frac{x_i}{t_i}$，其中 $\sum_{i=1}^{j-1}\frac{x_i}{t_i}$ 为小于 $j$ 的所有任务的 $\frac{x_i}{t_i}$ 的和。在从小到大扫描过程中可以开一个变量累加即可。 代码编写时注意浮点数和整数之间的运算问题，注意开double。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
struct node {
	int a,t,x;
}a[N];
bool cmp(node l,node r){
	return l.x<r.x;
}
double ans,sum;
int main(){
	cout<<fixed<<setprecision(8);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].a>>a[i].t>>a[i].x;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		ans+=a[i].a;
		ans-=sum/a[i].t;
		sum+=(double)a[i].x/a[i].t;
	}
	cout<<ans;
}

数据分析

题意：给定一个长度为 $n$ 的数组，求出所有长度为 $k$ 的区间的第 $\frac{k}{3}$ 大数字是多少

题解：使用一个对顶堆维护，大根堆维护最小的 $\frac{k}{3}$ 个数，小根堆维护剩余的数字，这样能保证任何时刻，第 $\frac{k}{3}$ 个数一定是大根堆的堆顶。插入时删除时打上标记，更改有效数字的大小。

#include<iostream>
#include<queue>
using namespace std;
using pii=pair<int,int>;
const int N=1000005;
int n,k; 
int a[N];
int sz1=0,sz2=0;
priority_queue<pii>q1;//大根堆
priority_queue<pii,vector<pii>,greater<pii>>q2;//小根堆
void adjust(int nowl,int nowr){
    while(sz1<k/3){
        pii t=q2.top();
        q2.pop();
        if(t.second<nowl)continue;
        sz2--;
        q1.push(t);
        sz1++;
    }
    while(sz1>k/3){
        pii t=q1.top();
        q1.pop();
        if(t.second<nowl)continue;
        sz1--;
        q2.push(t);
        sz2++;
    }
    while(q1.top().second<nowl){
        q1.pop();
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=k;i++){
        q1.push({a[i],i});
        sz1++;
    }
    adjust(1,k);
    cout<<q1.top().first<<"\n";
    for(int l=2,r=k+1;r<=n;r++,l++){
        if(a[r]>=q2.top().first){
            sz2++;
            q2.push({a[r],r});
        }
        else {
            sz1++;
            q1.push({a[r],r});
        }

        if(a[l-1]<=q1.top().first){
            sz1--;
        }
        else{
            sz2--;
        }
        adjust(l,r);
        cout<<q1.top().first<<"\n";
    }
}