Loading...

选择客栈 洛谷P1311

check评论:0 条 remove_red_eye浏览量:429 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-06-16

题意简述:在在一个序列中,每个点都有一个标识符(颜色)以及值,求出有多少对无序点对使得颜色相同的两点之间至少有一个点的值小于标准值?
输入:点个数,标识符最大值,标准值。
输出:无序点对个数

思路0:
暴力枚举,暴力找最小值,预计得分0~40
思路0.5:
加一些没啥用的优化,预计得分0~40
思路1:
因为标识符均在50以内,所以想到开一个vector<int> color[50],存储每一种标识符都有哪些点(按照输入顺序存)
然后线段树维护区间最小值,每次查询两个同颜色点对间最小值是否小于标准值 
预计得分60
code:
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> color[50];
int p[200010],sum[800010];
#define pushup(o) sum[o]=min(sum[o<<1],sum[o<<1|1])
void build(int o,int lf,int rg)
{
    if(lf==rg)
    {
        sum[o]=p[lf];
        return ;
    }
    int mid=(lf+rg)>>1;
    build(o<<1,lf,mid);
    build(o<<1|1,mid+1,rg);
    pushup(o);
}
int query(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        return sum[o];
    }
    int ans=0x3f3f3f3f;
    int mid=(lf+rg)>>1;
    if(l<=mid)
    {
        ans=min(ans,query(o<<1,lf,mid,l,r));
    } 
    if(mid<r)
    {
        ans=min(ans,query(o<<1|1,mid+1,rg,l,r));
    }
    return ans;
}
int main()
{
    int n,k,w;
    cin>>n>>k>>w;
    for(int i=1;i<=n;i++)
    {
        int c;
        scanf("%d%d",&c,&p[i]);
        color[c].push_back(i);
    }    
    build(1,1,n);
    int ans=0;
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<color[i].size()-1;j++)
        {
            for(int l=j+1;l<color[i].size();l++)
            {
                if(query(1,1,n,color[i][j],color[i][l])<=w)
                {
                    ans++;
                }
            }
        }
    }
    cout<<ans;
} 
思路1.5:
思考到,对于这一段代码
for(int i=0;i<k;i++)
{
    for(int j=0;j<color[i].size()-1;j++)
    {
        for(int l=j+1;l<color[i].size();l++)
        {
            if(query(1,1,n,color[i][j],color[i][l])<=w)
            {
                ans++;
            }
        }
    }
}
可以进行优化,如果我在区间[l,r]中已经找到了小于标准值的值,那么在[l,r+n](n>0)的区间内也必定可以找到
则此段代码改为
for(int i=0;i<k;i++)
{
    for(int j=0;j<color[i].size()-1;j++)
    {
        for(int l=j+1;l<color[i].size();l++)
        {
            if(query(1,1,n,color[i][j],color[i][l])<=w)
            {
                ans+=color[i].size()-l;//后面都无需查询,必定是可以的
                l=color[i].size();//结束最内层循环
            }
        }
    }
}
预计得分100
code:
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> color[50];
int p[200010],sum[800010];
#define pushup(o) sum[o]=min(sum[o<<1],sum[o<<1|1])
void build(int o,int lf,int rg)
{
    if(lf==rg)
    {
        sum[o]=p[lf];
        return ;
    }
    int mid=(lf+rg)>>1;
    build(o<<1,lf,mid);
    build(o<<1|1,mid+1,rg);
    pushup(o);
}
int query(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        return sum[o];
    }
    int ans=0x3f3f3f3f;
    int mid=(lf+rg)>>1;
    if(l<=mid)
    {
        ans=min(ans,query(o<<1,lf,mid,l,r));
    } 
    if(mid<r)
    {
        ans=min(ans,query(o<<1|1,mid+1,rg,l,r));
    }
    return ans;
}
int main()
{
    int n,k,w;
    cin>>n>>k>>w;
    for(int i=1;i<=n;i++)
    {
        int c;
        scanf("%d%d",&c,&p[i]);
        color[c].push_back(i);
    }    
    build(1,1,n);
    int ans=0;
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<color[i].size()-1;j++)
        {
            for(int l=j+1;l<color[i].size();l++)
            {
                if(query(1,1,n,color[i][j],color[i][l])<=w)
                {
                    ans+=color[i].size()-l;
                    l=color[i].size();
                }
            }
        }
    }
    cout<<ans;
} 
思路2:
从1到n枚举,我们需要记录一个距离第二个客栈最近的咖啡厅价钱合理的客栈位置,用一个lt变量记录。
开三个辅助数组,pos[i]表示最后一个以i为颜色的客栈的位置,sum[i]表示以i为颜色的客栈总数,last[i]可以看作是一个临时数组,用来存储当前的方案数。
可以这么想,当前枚举到一个客栈i,这个i是第二个客栈,那么显然第一个客栈一定在第二个客栈之前,编号必定是0~i-1之间的一个数。如果我发现枚举的时候在某一个客栈前面有一个价钱合理的咖啡厅,那么在这之前的任何一个同色客栈都是第一个客栈可以选的,那么统计一下数量,这就是当前的方案数。
然后更新pos数组,更新ans,让sum[color]++,这样从左到右地推过来就好了。
这个解法简化于暴力算法,暴力算法要循环三层,一层1客栈,二层2客栈,3层合理的位置,这样做显然不行,而我们做的就是去优化掉两层,而是从枚举2客栈出发推出1客栈的位置和所有可行方案,所以这样做是正确的。最后输出即可。
code:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 210000
inline int read()
{
    int x=0,t=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
    {
        ch=getchar();
    } 
    if(ch=='-')
    {
        t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*t;
}
int n,k,p,tot,lt,sum[N],last[N],ans,pos[N];
int main()
{
    n=read();
    k=read();
    p=read();
    for(int i=1;i<=n;++i)
    {
        int c=read();
        int v=read();
        if(v<=p)
        {
            lt=i;
        }
        if(pos[c]<=lt)
        {
            last[c]=sum[c];
        }
        ans+=last[c];
        sum[c]++;
        pos[c]=i;
    }
    printf("%d\n",ans);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名