网易2018.3.27编程题

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。

对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。

3 3
1 100
10 1000
1000000000 1001
9 10 1000000000

100
1000
1001

题解：将工作的难度和薪酬作为一个结构体，然后以工作难度升序，薪酬降序排序，之后由于题目未说明难度大的工作一定薪酬高，所以重新扫描一遍数组然后将难度为d的工作的薪酬设置为能获得最高薪酬。最后就是二分找小于等于key的最后一个元素的下标，对应的薪酬就是能够得到的最高薪酬，O（nlogn）

坑点：

1. 题中没说难度大的薪酬就高

2. 存在一个人的能力比最低功能难度还要低，也存在一个人的能力比最高难度还要高，所以二分的过程要注意

代码：

#include<iostream>
#include<fstream>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<utility>
#include<algorithm>
#include<map>
#include<stack>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const int INF = 1<<30;
struct work
{
int d, p;
}arr[maxn];
int A[maxn], ans[maxn], N, M;
bool cmp(const work w1, const work w2)
{
if(w1.d != w2.d)
return w1.d<w2.d;
return w1.p>w2.p;
}
int getIndex(int k)
{
int lower=0, higher=N;
while(lower < higher)
{
int mid = (lower+higher+1)>>1;//这里用的是偏大的中位数，为了逼近最后一个符合的条件的值
if(arr[mid].d <= k)
lower = mid;
else
higher = mid-1;
}
return lower;//是lower逼近答案的,higher只是负责缩小解空间，其实他们的值都是相同的
}
int main( )
{
//freopen("input.txt", "r", stdin);
while(~scanf("%d%d", &N, &M))
{
for(int i=1; i<=N; i++)
scanf("%d%d", &arr[i].d, &arr[i].p);
for(int i=0; i<M; i++)
scanf("%d", A+i);
sort(arr+1, arr+N+1, cmp);
arr[0].d = 0, arr[0].p = 0;
for(int i=1; i<=N; i++)//处理得到i对应的能力能获得的最高薪酬
{
arr[i].p = max(arr[i].p, arr[i-1].p);
}
for(int i=0; i<M; i++)
{
int index = getIndex(A[i]);
ans[i] = arr[index].p;
}
for(int i=0; i<M; i++)
cout<<ans[i]<<endl;
}
return 0;
}

输入包括五行。
第一行包括一个整数n(2 <= n <= 50), 表示矩形的个数。
第二行包括n个整数x1[i](-10^9 <= x1[i] <= 10^9),表示左下角的横坐标。
第三行包括n个整数y1[i](-10^9 <= y1[i] <= 10^9),表示左下角的纵坐标。
第四行包括n个整数x2[i](-10^9 <= x2[i] <= 10^9),表示右上角的横坐标。
第五行包括n个整数y2[i](-10^9 <= y2[i] <= 10^9),表示右上角的纵坐标。

输出一个正整数, 表示最多的地方有多少个矩形相互重叠,如果矩形都不互相重叠,输出1。

2
0 90
0 90
100 200
100 200

2

题解：首先要理解这个重叠的意思，就是n个矩形都公用这一块面积才是重叠，那么我只需要用四个int，x1,y1,x2,y2维护当前被重叠的面积，然后每当有一个新的矩形包含了这个区域就计数，并且更新这四个变量，然后对每一个矩形都进行一次扫描，在O(n^2)的时间内就可以完成， 但是需要先排序，否则枚举的过程可能会丢掉最优解。

代码：

#include<iostream>
#include<fstream>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<utility>
#include<algorithm>
#include<map>
#include<stack>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 55;
const int mod = 1e9+7;
const int INF = 1<<30;
struct node
{
int x1, x2, y1, y2;
bool operator<(const node& node1) const{
if(x1 != node1.x1)
return x1<node1.x1;
if(y1 != node1.y1)
return y1<node1.y1;
if(x2 != node1.x2)
return x2<node1.x2;
return y2<node1.y2;
}
}arr[maxn];
int n;
int main( )
{
//freopen("input.txt", "r", stdin);
while(~scanf("%d", &n))
{
for(int i=0; i<n; i++)
scanf("%d", &arr[i].x1);
for(int i=0; i<n; i++)
scanf("%d", &arr[i].y1);
for(int i=0; i<n; i++)
scanf("%d", &arr[i].x2);
for(int i=0; i<n; i++)
scanf("%d", &arr[i].y2);
sort(arr, arr+n);
int ans = 0;
for(int i=0; i<n; i++)
{
int counter = 0, x1=arr[i].x1, x2=arr[i].x2, y1=arr[i].y1, y2=arr[i].y2;
for(int j=0; j<n; j++)
{
if(arr[j].x1<x2 && arr[j].y1<y2 && arr[j].x2>x1 && arr[j].y2>y1)
{
x1 = max(x1, arr[j].x1);
y1 = max(y1, arr[j].y1);
x2 = min(x2, arr[j].x2);
y2 = min(y2, arr[j].y2);
counter++;
}
}
ans = max(ans, counter);
}
cout<<ans<<endl;
}
return 0;
}

输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。

对于每个测试用例, 输出一个正整数表示可能的数对数量。

5 2

7

满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)

题解：先想到暴力，分别枚举余数，除数，商，但是一定会超时的。那就要进行优化，利用除数，商，余数他们直接的关系，可以只对除数进行枚举，然后计算出可能的余数数量，商数量，然后特殊情况特判一下就好了。代码的注释写的很详细。

注意点：答案用long long

代码：

#include<iostream>
#include<fstream>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<utility>
#include<algorithm>
#include<map>
#include<stack>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 55;
const int mod = 1e9+7;
const int INF = 1<<30;
int n, k;
int main( )
{
//freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &k);
ll ans = 0;
for (int y=k+1; y<=n; y++)//枚举除数y
{
int quotientNumber = n / y;//当前除数的商的最多可能数量
int remainderNumber = y - k;//当前除数的余数最多可能数量
//当商在0-quotientNumber-1之间的时候，被除数自适应保证余数都能被取到，故
ans += ll(quotientNumber*remainderNumber);
//当余数的最小为0时，被除数最小不能为0，故
if(k == 0)
ans--;
//当商取为quotientNumber的时候，此时余数的数量会受到限制，故
ans += max(n%y-k+1, 0);
}
cout << ans << endl;
return 0;
}

最后

以上就是酷酷鼠标为你收集整理的网易2018.3.27编程题的全部内容，希望文章能够帮你解决网易2018.3.27编程题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。