10.07题解

· · 个人记录

10.07题解

今日保龄。

（欲说还休，却道天凉好个秋。）

1.松鼠聚会：

关键：切比雪夫距离转曼哈顿距离。

笔记本上以及洛谷题解都有详细证明，此处不再过多赘述。

求平面上一个点到多个点的曼哈顿距离之和，将绝对值拆开，转化成前缀和的形式，即可。

2.拯救小矮人：

贪心解法：

将小矮人的(a+b) 从小到大排好序，因为(a+b) 越小，自己就越难逃生，就越站在上面越好。然后能跑出去就跑。

然后就WA了，这种弱智的贪心法明显是不配成为蓝题的，我们考虑一下情况：已经跑出去了一个身高是100的人，当前在判断的人的高度是10，如果交换两人位置后，10的人能跑出去，100不行了，那么交换一定更优，因为最后跑不出去的人都只有一个，要么10，要么100，那么我为什么不把100的人垫在下面。这叫做可悔贪心，我们发现了，前面某个决策不那么优，就重新决策。

故我们用一个堆去维护前面跑出去人的最大值，如果一个人跑不出去了，就把最大的人拉回来看能不能把当前这个人跑出去，如果还跑不出去，那就把最高的人放回去，如果二换一就不值了。

#include<bits/stdc++.h>
#include<queue>
using namespace std;
template<typename W>inline void rd(W &x){
    W ch=getchar(),tx=1;x=0;
    while(!isdigit(ch)) tx=ch=='-'?-1:tx,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x=tx*x;
}
const int N=2010;
int n,h,s[N],tot[N],pre_h,k;
struct node{
    int a,b,sum;
    bool operator<(const node &x)const{return x.a>a;}
}p[N];
bool cmp(node x,node y){
    if(x.sum==y.sum) return x.a<y.a;
    else return x.sum>y.sum;
}
priority_queue<node>q;

int main(){
    pre_h=k=0;
    rd(n);
    for(int i=1;i<=n;++i){
        rd(p[i].a),rd(p[i].b);
        p[i].sum=p[i].a+p[i].b;
        pre_h+=p[i].a;
    }
    rd(h);
    sort(p+1,p+n+1,cmp);
    int i=n;
    while(i!=0){
        if(pre_h+p[i].b>=h) q.push(p[i]),pre_h-=p[i--].a;
        else if(!q.empty()){
            if(pre_h+q.top().a+p[i].b>=h){
                if(q.top().a>p[i].a){
                    pre_h+=q.top().a-p[i].a;
                    q.pop();
                    q.push(p[i]);--i,++k;
                }
                else --i,++k;
            }
            else --i,++k;
        }
        else --i,++k;
    }
    printf("%d",n-k);
}

3.最长上升子序列：

数据结构大杂烩，第一步处理：构造出原序列。因为每次都是强行插入，所以用n^2去维护可定是没法过得，但是，STL可以。用STL中的vector中的insert即可在时限内构造出原序列，理论来讲vector也是n^2每次插入也是n，但他就是能过，所以就用吧！其实也可以用平衡树去实现插入，但蒻蓟不会，故直接用STL了。

第二步处理：求动态LIS。我们现在已经搞到了原序列，我们考虑将每个数在原序列中的位置记下来，方便我们直接访问，并从小到大放入去模拟题目中的放入。我们利用本题插入的性质，数字从小到大，从1到n，依次插入。那么一个数插到中间某个位置一定不会影响后面的状态，因为他比后面的数都大，他也自然无法接上后面的上升序列，他也自然可以接上前面所有数的的上升序列。所以每个数插进数组时我们去找他位置前面的最大值，在加一，与当前最大DP比较，更新答案，在将这个新DP值放入线段树中即可。

#include<bits/stdc++.h>
#include<vector>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
template<typename W>inline void rd(W &x){
    W ch=getchar(),tx=1;x=0;
    while(!isdigit(ch)) tx=ch=='-'?-1:tx,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x=tx*x;
}
const int N=100010;
int ans,n,p[N];
vector<int>s;

struct SegmentTree{
    int mid,dat[N<<2],lf[N<<2],rt[N<<2];
    void build(int w,int l,int r){
        lf[w]=l,rt[w]=r;
        if(l==r) return;
        int mid=l+r>>1;
        build(ls(w),l,mid);
        build(rs(w),mid+1,r);
        return;
    }
    void update(int w,int pos,int k){
        if(lf[w]==rt[w]){dat[w]=k;return;}
        int mid=lf[w]+rt[w]>>1;
        if(pos<=mid) update(ls(w),pos,k);
        else update(rs(w),pos,k);
        dat[w]=max(dat[ls(w)],dat[rs(w)]);
        return;
    }
    int ask(int w,int l,int r){
        if(lf[w]>r||rt[w]<l||l>r) return -1;
        if(l<=lf[w]&&rt[w]<=r) return dat[w];
        return max(ask(ls(w),l,r),ask(rs(w),l,r));
    }
}Stree;

int main(){
    int tmp; rd(n); 
    for(int i=1;i<=n;++i){rd(tmp);s.insert(tmp+s.begin(),i);}
    for(int i=1;i<=n;++i) p[s[i-1]]=i;
    Stree.build(1,1,n);
    for(int i=1;i<=n;++i){
        tmp=Stree.ask(1,1,p[i])+1;
        ans=max(tmp,ans);
        Stree.update(1,p[i],tmp);
        printf("%d\n",ans);  
    }
    return 0;
}