hihocoder编程练习赛50

自用笔记算法

hihocoder编程练习赛50

A

描述
给定包含N个整数的数组A1, A2, … AN，你可以选择任意一个Ai，将Ai旋转到数组第一项，即将数组变成：
Ai, Ai+1, Ai+2, … AN, A1, A2, …, Ai-1
现在小Hi希望旋转之后的数组满足：
对于任意K(1 ≤ i ≤ N)，前K项的和都是正数。
例如对于A=[3, -5, 2, -2, 3, 0]，旋转成[3, 0, 3, -5, 2, -2]满足条件。
请你输出i，代表将Ai旋转到第一项满足条件。
如果有多解，你可以输出任意一个i。如果无解输出-1。

输入
第一行包含一个整数N。
第二行包含N个整数A1, A2, … AN。
对于50%的数据，1 ≤ N ≤ 1000
对于100%的数据，1 ≤ N ≤ 100000, -1000000 ≤ Ai ≤ 1000000

输出
一个整数表示答案。

样例输入
6
3 -5 2 -2 3 0

样例输出
5

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define maxn 200050
#define LL long long 
using namespace std;
const LL INF =(LL)1e18;
int n;
int a[maxn];
LL sum[maxn];
bool check(int x){
	LL sum=0;
	for(int i=x+1;i<=x+1+n;i++){
		sum+=a[i];
		if(sum<=0) return false;
	}
	return true;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	memset(sum,0,sizeof sum);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+(LL)a[i];
	}
	for(int i=n+1;i<=n+n;i++) a[i]=a[i-n];
	LL Min=INF;
	int id=1;
	for(int i=1;i<=n;i++){
		if(sum[i]<=Min){
			Min=sum[i];
			id=i;
		}
	}
	if(check(id)) printf("%d\n",id+1);
	else puts("-1");
	return 0;
}

思路

贪心
寻找前缀和最小的最后一个位置 然后判断把后面所有的数字全部放到开头 判断是否满足要求
这样的贪心结果可以满足后面的数字和最大

B

描述
HIHO银行等待区有一排N个座位，从左到右依次编号1~N。现在有M位顾客坐在座位上，其中第i位坐在编号Ai的座位上。
之后又陆续来了K位顾客，(K + M ≤ N) 他们都会选择坐在最”舒适”的空座位上，并且过程中没有顾客离开自己的座位。
最”舒适”的定义是：

  1. 对于一个座位，我们将它左边连续的空座位数目记作X，它右边连续的空座位数目记作Y。
  2. 顾客首先会选择min(X, Y)最大的座位。
  3. 如果有多个选择，顾客会选择其中max(X, Y)最大的座位。
  4. 如果还是有多个选择，顾客会选择其中编号最小的座位。
    请你计算出之后来的K位顾客坐在几号座位上。

输入
第一行包含三个整数N，M和K。
第二行包含M个整数A1, A2, … AM。
对于50%的数据，1 ≤ N ≤ 1000
对于100%的数据，1 ≤ N ≤ 100000, 1 ≤ Ai ≤ N, K + M ≤ N

输出
输出K行，每行一个整数代表该位顾客座位的编号。

样例输入
10 2 3
1 10

样例输出
5
7
3

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define maxn 100050
using namespace std;
int n,m,k;
int a[maxn],l[maxn],r[maxn];
struct node{
	int val,l,r;
	node(int val,int l,int r):val(val),l(l),r(r){}
	bool operator < (const node x) const{
		if(min(l,r)!=min(x.l,x.r)) return min(l,r)>min(x.l,x.r);
		if(max(l,r)!=max(x.l,x.r)) return max(l,r)>max(x.l,x.r);
		return val<x.val;
	}
};
set<node>s;
int main(){
	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d",&n,&m,&k)!=EOF){
		for(int i=1;i<=m;i++){
			int x;
			scanf("%d",&x);
			a[x]++;
		}
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		s.clear();
		for(int i=2;i<=n;i++){
			if(a[i]==0 && a[i-1]==0) l[i]=l[i-1]+1;
		}
		for(int i=n-1;i>=1;i--){
			if(a[i]==0 && a[i+1]==0) r[i]=r[i+1]+1;
		}
		for(int i=1;i<=n;i++){
			if(a[i]==0){
				s.insert(node(i,l[i],r[i]));
			}
		}
		for(int i=1;i<=k;i++){
			node tmp=*s.begin();
			printf("%d\n",tmp.val);
			for(int j=tmp.val-1;j>=tmp.val-tmp.l;j--){
				s.erase(node(j,l[j],r[j]));
				r[j]-=tmp.r+1;
				s.insert(node(j,l[j],r[j]));
			}
			for(int j=tmp.val+1;j<=tmp.val+tmp.r;j++){
				s.erase(node(j,l[j],r[j]));
				l[j]-=tmp.l+1;
				s.insert(node(j,l[j],r[j]));
			}
			s.erase(tmp);
		}
	}
	return 0;
}

思路

stl模拟优先级
原本用优先队列写的 结果发现优先队列里没有迭代器 所以在k个人依次选择到自己的位置后 不会更新l和r数组
参考了别人的代码发现用set即可 先删除原本的位置 再更新l和r数组 再insert回去
注意l和r数组的更新为：坐下位置的l或r值+1
注意set的begin返回的是一个迭代器指针类型 加上星号才能变成node类型
补：题目的实质是找出最长区间 坐在中点位置 优先队列存放区间长度即可 维护一个l r和mid 每次弹出一个最长的区间 然后把该区间分成两半再push进去

C

cf原题
转跳连接

本文标题:hihocoder编程练习赛50

文章作者:Hippopmonkey

发布时间:2018-03-14, 20:53:04

最后更新:2018-03-14, 21:13:50

原始链接:http://xuboming8.github.io/2018/03/14/hihocoder编程练习赛50/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. hihocoder编程练习赛50
    1. 1.1. A
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
    2. 1.2. B
      1. 1.2.1. 参考AC代码
      2. 1.2.2. 思路
    3. 1.3. C
|