nefu 1535 我喜欢查找

#include <bits/stdc++.h>
using namespace std;
map<int,int>vis;
int n,m,x,a[100010];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        vis[x]++;
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x;
        i==m?printf("%d\n",vis[x]):printf("%d ",vis[x]);
    }
    return 0;
}

nefu 1536 这几天喜欢绝对值

n=1e6,O(n*logn)还是能过的,数据规模小于2e7(1秒大概能跑2e7的数据)

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define min3(a,b,c) min(min(a,b),c)//定义三个数的最小值
int n,x,k,cnt1,cnt2,ans,a[N],b[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(x>=0)a[++cnt1]=x;//a数组中储存正数
        else b[++cnt2]=x;//b数组中储存负数
    }
    sort(b+1,b+cnt2+1);
    ans=0x3f3f3f3f;
    for(int i=1;i<=cnt1;i++)
    {
        k=lower_bound(b+1,b+cnt2+1,-a[i])-b;//不是-b-1,而是直接-b
        if(k==cnt2+1){ans=min(ans,abs(a[i]+b[cnt2]));continue;}
        //如果在b数组中没有找到大于等于-a[i]的数,则k=cnt2+1,此时abs(a[i]+b[cnt2])最小
        ans=min3(ans,abs(a[i]+b[k]),abs(a[i]+b[k-1]));
    }
    printf("%d\n",ans);
    return 0;
}

nefu 1537 买饭-优先队列

1、结构体数组排序做法。

#include <bits/stdc++.h>
using namespace std;
double ans;
int n,sum;
struct node
{
    int x,num;
}a[1010];
bool cmp(node s1,node s2)
{return s1.x<s2.x;}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x;
        a[i].num=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        i==n?printf("%d\n",a[i].num):printf("%d ",a[i].num);
    for(int i=2;i<=n;i++)
    {
        sum+=a[i-1].x;
        ans+=sum;
    }
    printf("%.2lf\n",(double)ans/n);
    return 0;
}

2、优先队列做法。

掌握结构体优先队列自定义排序的写法:

struct node
{
    int x,num;
};
bool operator < (const node &s1,const node &s2)//重载运算符,自定义排序
{
    if(s1.x!=s2.x)return s1.x>s2.x;//与实际应该写的<号相反
    else if(s1.num!=s2.num) return s1.num>s2.num;//与实际应该写的<号相反
    //else if 这句排序很重要!(数组排序的时候默认有这句话,但是优先队列没有)
}
priority_queue<node>q;

完整代码:

#include <bits/stdc++.h>
using namespace std;
double ans;
int n,x,sum;
struct node
{
    int x,num;
};
bool operator < (const node &s1,const node &s2)
{
    if(s1.x!=s2.x)return s1.x>s2.x;
    else if(s1.num!=s2.num) return s1.num>s2.num;
    //else if 这句排序很重要!(数组排序的时候默认有这句话,但是优先队列没有)
}
priority_queue<node>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        q.push({x,i});
    }
    for(int i=1;i<=n;i++)
    {
        i==n?printf("%d\n",q.top().num):printf("%d ",q.top().num);
        if(i<n){sum+=q.top().x;ans+=sum;}
        q.pop();
    }
    printf("%.2lf\n",(double)ans/n);
    return 0;
}

nefu 1534 暴力出奇迹

容易想到O(n^2^)的暴力,也就是枚举所有可能的区间。数据规模达到1e8,显然TLE。(林大oj 1秒大概能跑2e7)

稍加优化,先求出所有区间内的最大值mx以及它对应的区间长度mxlen,当要查询的区间长度x<=mxlen时,区间可以取到最大值mx,直接输出答案。

当要查询的区间长度x>mxlen时,还是得O(n^2^)暴力...(所以我感觉优化得还不够彻底,但是还是过了...)

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,m,x,t,mx,cnt,tmp,mxlen,a[N],sum[N],ans[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    mx=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];//前缀和
        if(tmp<0)
        {
            tmp=a[i];
            cnt=1;
        }
        else
        {
            tmp+=a[i];
            cnt++;
        }
        if(tmp>mx)
        {
            mx=tmp;//mx表示所有区间内的最大值
            mxlen=cnt;//mxlen表示区间最大值mx对应的区间长度
        }
    }
    memset(ans,-0x3f,sizeof(ans));
    for(int k=mxlen+1;k<=n;k++)//枚举区间长度,其实也就是O(n^2)的暴力打表
        for(int i=1;i<=n-k+1;i++)//枚举左端点i,右端点为i+k-1
            ans[k]=max(ans[k],sum[i+k-1]-sum[i-1]);
            //ans[k]表示长度为k的所有区间中的最大值
    while(m--)
    {
        cin>>x;
        if(x<=mxlen)printf("%d\n",mx);//x<=mxlen时,可以取到所有区间的最大值
        else//其他情况则必须找最大值
        {
            t=-0x3f3f3f3f;
            for(int i=x;i<=n;i++)
                t=max(t,ans[i]);
            printf("%d\n",t);
        }
    }
    return 0;
}