网易2018.03.27算法岗，三道编程题100%样例AC题解

博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~
http://www.cnblogs.com/chenxiwenruo/p/8660814.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~

1. 自定义排序

第一题是第一行给出n(1<=n<=100)，表示下面有n行，每行A(0<=A<24)和B(0<=B<60)，表示定的闹钟为AhBmin。

接下来给定X，表示小明从起床到教室需要X分钟，最后一行给出A(0<=A<24)和B(0<=B<60)表示上课时间AhBmin。

求问小明赶在上课前，能够定的最晚闹铃时间为多少，样例保证必定有一个符合要求。

　对闹铃排序，按照A从小到大排序，当A相同的时候，B从小到大排序，然后从最后一个往回遍历，找到距离上课时间>=Xmin中的闹铃时间，输出即可。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <string.h>

/*

3

5 0

6 0

7 0

59

6 59

*/

using namespace std;

const int maxn=;

struct Node{

    int h;

    int m;

    bool operator<(const Node tmp)const{

        if(h==tmp.h)

            return m<tmp.m;

        else

            return h<tmp.h;

    }

};

Node clocks[maxn];

int n;

int main()

{

    int a,b;

    scanf("%d",&n);

    for(int i=;i<n;i++){

        scanf("%d %d",&clocks[i].h,&clocks[i].m);

    }

    sort(clocks,clocks+n);

    int x;

    scanf("%d",&x);

    scanf("%d %d",&a,&b);

    for(int i=n-;i>=;i--){

        if(clocks[i].h>a)

            continue;

        if(clocks[i].h==a){

            if(b-clocks[i].m>=x){

                printf("%d %d\n",clocks[i].h,clocks[i].m);

                break;

            }

        }

        else{

            if(-clocks[i].m+(a-clocks[i].h-)*+b>=x){

                printf("%d %d\n",clocks[i].h,clocks[i].m);

                break;

            }

        }

    }

    return ;

}

2. 离散化+二分查找

对于一个矩阵，在坐标系内，左下角坐标(x1,y1)，右上角坐标(x2,y2)，现在给出n个矩阵的坐标，问重叠区域矩阵最多的个数？如果没有矩阵重叠，输出1。

输入样例，第一行n，接下来分别为n个x1，n个y1，n个x2，n个y2。1<=n<=50，-10^9<=xi,yi<=10^9。

很明显，n的范围只有50，数据量很小，但是x和y很大，需要离散化处理，这样的话最多200个不同的值。

处理之后，对于第i个矩阵，遍历它所在的范围，cnt[i][j]++即可。最后输出cnt最大的那个。如果cnt都为0，即没有矩阵，也就没有重叠，也输出1。

这里注意，一开始我在遍历的时候，下面for循环，起始条件没有+1，这样的话还有10%样例是过不了的。应该是统计边，而不是统计点，因为对于[(0,0),(0,0)]是构不成矩阵的。

for(int k=lx+;k<=rx;k++){

        for(int p=ly+;p<=ry;p++){

                cnt[k][p]++;

        }

}

完整代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <string.h>

using namespace std;

/*

2

0 90

0 90

100 200

100 200

*/

const int maxn=;

int n;

int xx1[maxn],xx2[maxn],yy1[maxn],yy2[maxn];

int idx=;

int a[maxn];

int hash_x[maxn];

int cnt[maxn][maxn];

int binarySearch(int *a,int t,int n){

    int l=,r=n-;

    int mid;

    while(l<=r){

        mid=(l+r)>>;

        if(a[mid]==t)

            return mid;

        if(t<a[mid])

            r=mid-;

        else

            l=mid+;

    }

    return -;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<n;i++){

        scanf("%d",&xx1[i]);

        a[i*+]=xx1[i];

    }

    for(int i=;i<n;i++){

        scanf("%d",&yy1[i]);

        a[i*+]=yy1[i];

    }

    for(int i=;i<n;i++){

        scanf("%d",&xx2[i]);

        a[i*+]=xx2[i];

    }

    for(int i=;i<n;i++){

        scanf("%d",&yy2[i]);

        a[i*+]=yy2[i];

    }

    //离散化，将-10^9~10^9的数据映射为0~200以内，因为最多出现4*50不同的数，映射值即为索引。

    sort(a,a+*n);

    hash_x[]=a[];

    idx=;

    for(int i=;i<*n;i++){

        if(a[i]!=a[i-]){

            hash_x[idx]=a[i];

            idx++;

        }

    }

    memset(cnt,,sizeof(cnt));

    for(int i=;i<n;i++){

        int lx,ly,rx,ry;

        //二分查找对应离散化后的索引。

        lx=binarySearch(hash_x,xx1[i],idx);

        ly=binarySearch(hash_x,yy1[i],idx);

        rx=binarySearch(hash_x,xx2[i],idx);

        ry=binarySearch(hash_x,yy2[i],idx);

        for(int k=lx+;k<=rx;k++){

            for(int p=ly+;p<=ry;p++){

                cnt[k][p]++;

            }

        }

    }

    int ans=;

    for(int i=;i<=idx;i++){

        for(int j=;j<=idx;j++){

            ans=max(ans,cnt[i][j]);

        }

    }

    if(ans==)

        ans=;

    printf("%d\n",ans);

    return ;

}

3. dfs+剪枝

第一行n和w，接下来有n个零食的重量v[i]，0<v[i]<10^9，问你在背包重量为w的情况下，最多能有几种装法？背包重量为0也算一种。

比如说

3 8

1 2 3

因为总的背包容量大于三个总重量，所以三个每个都可选可不选，共计2^3种。

先对零食的重量从小到大排序，然后从最后一个开始，零食索引为idx，背包剩余容量为left，现有方案总数为tot，初始为0。

1. 若idx<=0或者left<=0，表示没得选了，只有就这一种方案，所以tot++即可。

2. 若idx之前所有零食的总重量<=left，那么很显然，该方案数总共为2^idx，加到tot上即可。

3. 若v[idx]<=left，那么我可以放第idx个零食，方案数即为dfs(idx-1,left-v[idx])。

4. 当然不管怎样，我也可以选择不放第idx个零食，方案数即为dfs(idx-1,left)。

注意，因为零食重量的范围，所以代码里的two数组、sum数组、tot为long long，才不会溢出，否则样例会有不过。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <string.h>

using namespace std;

const int maxn=;

int n;

int v[maxn];

long long sum[maxn]; //sum[i]统计v[1]~v[i]的和

int w;

long long tot=;

long long two[]; //two[i]即为2^i值

//dfs搜索所有的方案数

void dfs(int idx,int left){

    if(idx<= || left<=){

        tot+=;

        return;

    }

    if(sum[idx]<=left){

        tot+=two[idx];

        return;

    }

    if(left>=v[idx]){

        dfs(idx-,left-v[idx]);

    }

    dfs(idx-,left);

}

int main()

{

    two[]=;

    for(int i=;i<=;i++)

        two[i]=two[i-]*;

    scanf("%d %d",&n,&w);

    for(int i=;i<=n;i++){

        scanf("%d",&v[i]);

    }

    sort(v+,v+n+);

    sum[]=;

    for(int i=;i<=n;i++){

        sum[i]=sum[i-]+v[i];

    }

    dfs(n,w);

    printf("%lld\n",tot);

    return ;

}

巴特西

网易2018.03.27算法岗，三道编程题100%样例AC题解

最新文章

热门文章