牛客网--今日头条2018校招算法方向（第一批）编程题1、编程题2

妖狐艹你老母 2024-02-18 17:27 18阅读 0赞

1、

\[编程题\] 编程题1

时间限制：1秒

空间限制：32768K

P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在\[0, 1e9) 内）

如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

![300557_1502940399706_1329AFEA3FC7961DEA219781A71B3B5B][]

###### 输入描述: ######

第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。
    对于 50%的数据,  1 <= N <= 10000;
    对于 100%的数据, 1 <= N <= 500000;

###### 输出描述: ######

输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。

###### 输入例子1: ######

5
    1 2
    5 3
    4 6
    7 5
    9 0

###### 输出例子1: ######

4 6
    7 5
    9 0

AC代码：

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int maxn = 5e5+5;
    struct node{
    	int x , y;
    	node(int x,int y):x(x),y(y){}
    	node(){}
    	bool operator<(const node& n)const {
    	  return this->x < n.x;
    	} 
    };
    
    struct node nd[maxn];
    int flag[maxn];
     
    int main(){
    	int n;
    	while(scanf("%d",&n) == 1){
    		for(int i = 0; i < n; i++)
    		scanf("%d%d",&nd[i].x,&nd[i].y);
    		
    		sort(nd,nd+n);
    		memset(flag,0,sizeof(flag));
    		
    		flag[n-1] = 1;
    		int Max1 = nd[n-1].y;
    		for(int i = n-2; i >= 0; i--){
    			if(nd[i].y < Max1) continue;
    			Max1 = nd[i].y;
    			flag[i] = 1;
    		}
    		
    		for(int i = 0; i < n; i++){
    			if(flag[i])printf("%d %d\n",nd[i].x,nd[i].y);
    		} 
    
    	}
    	return 0;
    }

2、

\[编程题\] 编程题2

时间限制：3秒

空间限制：131072K

给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：

区间中的最小数 \* 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列 \[6 2 1\]则根据上述公式, 可得到所有可以选定各个区间的计算值:

\[6\] = 6 \* 6 = 36;

\[2\] = 2 \* 2 = 4;

\[1\] = 1 \* 1 = 1;

\[6,2\] = 2 \* 8 = 16;

\[2,1\] = 1 \* 3 = 3;

\[6, 2, 1\] = 1 \* 9 = 9;

从上述计算可见选定区间 \[6\] ，计算值为 36， 则程序输出为 36。

区间内的所有数字都在\[0, 100\]的范围内;

###### 输入描述: ######

第一行输入数组序列长度n，第二行输入数组序列。
    对于 50%的数据,  1 <= n <= 10000;
    对于 100%的数据, 1 <= n <= 500000;

###### 输出描述: ######

输出数组经过计算后的最大值。

###### 输入例子1: ######

3
    6 2 1

###### 输出例子1: ######

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 5e5+10;
    int a[maxn];
    int n;
    
    int main(){
    	while(scanf("%d",&n) == 1){
    		
    		for(int i = 1; i <= n; i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		
    		int Max1 = 0;
    		for(int i = 1; i <= n; i++){
    			int Min1 = a[i];
    			int sum = a[i];
    			for(int j = i-1; j >=1; j--){
    				if(a[j] >= Min1)  sum += a[j];
    				else break;
    			}
    			
    			for(int j = i+1; j <=n; j++){
    				if(a[j] >= Min1)  sum += a[j];
    				else break;				
    			}
    			Max1 = max(Max1,sum * Min1);
    		}
    		
    		printf("%d\n",Max1);
    	}	
    	return 0;
    }

[300557_1502940399706_1329AFEA3FC7961DEA219781A71B3B5B]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/31f4b9bd4a7442ce8eb400ebb96360a5.png