1159 B
题意
给你一个序列 (a(a_ile 10^9)) ，长度 (nle 10^5) ，求 ( ext{floor}(min(frac{min(a_i,a_j)}{|i-j|})))
Examples
input
4
6 4 5 5
output
1
input
3
0 1 2
output
0
input
4
821 500 479 717
output
239
解
对于每个固定的 (a_i) ，我们要么把它和 (a_1) 搭配，要么和 (a_n) 搭配，这样答案才能最小。
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=300003;
int n,a,ans=INF;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a);
ans=min(ans,a/max(i-1,n-i));
}
printf("%d
",ans);
return 0;
}
1159 C
题意
(n) 个男孩给 (m) 个女孩分糖果，设第 (i) 个男孩给第 (j) 个女孩 (a_{i,j}) 个糖果，你会得到两个数组 (b,g) ， (b_i=min_j(a_{i,j}),g_j=max_i(a_{i,j})) ，问可能的最少的男孩给女孩的糖果数总和是多少。
Examples
inputCopy
3 2
1 2 1
3 4
output
12
input
2 2
0 1
1 0
output
-1
input
2 3
1 0
1 1 2
output
4
解
思路全在代码里
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=100003,INF=1050000000;
int n,m;
long long a[maxn],b[maxn],suma,sumb,mxa=-INF,semxa=-INF,mib=INF;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",a+i),suma+=a[i];
if(a[i]>=mxa)semxa=mxa,mxa=a[i];
else if(a[i]>=semxa)semxa=a[i];
}
for(int i=1;i<=m;i++)scanf("%lld",b+i),sumb+=b[i],mib=min(mib,b[i]);
if(mxa>mib){puts("-1");return 0;}
printf("%lld
",suma*m+sumb-mxa*m+(mxa==mib?0:mxa-semxa));
return 0;
}
1159 D
题意
给你两个数 (n,k(n\% 2=k\% 2)) ，构造一个01串，长度为 (n) ，使得最短的只出现一次的子串长度为 (k) 。
解
乱搞。先 ((n-k)/2) 个1，然后1个0，如此往复。
1159 E
题意
你有一个长度为 (n) 的数组 (next[]) ， (next[i]) 表示满足条件的最小的 (j) ，使得 (i<j) 且 (p_i<p_j) 。现在你要构造一个长度为 (n) 的排列 (p) 使得 (next[]) 合法。不存在输出 (-1) 。多组数据。 ((sum nle 5*10^5))
Example
input
6
3
2 3 4
2
3 3
3
-1 -1 -1
3
3 4 -1
1
2
4
4 -1 4 5
output
1 2 3
2 1
2 1 3
-1
1
3 2 1 4
解
对于每个 (i) 连边 ((next[i],i)) 。（要多加一个编号为 (n+1) 的点）
如果加入边 ((i,i+1)) 后原图存在拓扑序，那么连边。
最后对这个有向图拓扑排序。
1159 F
题意
平面上有 (n) 个点，现在你要从某一个点依次经过所有点（每个点必须恰好经过一次），拐弯的顺序满足输入中给定的字符串。
Examples
input
3
1 1
3 1
1 3
L
output
1 2 3
input
6
1 0
0 1
0 2
-1 0
-1 -1
2 1
RLLR
output
6 1 3 4 2 5
Hint
解
首先对所有点按坐标排序，然后贪心选取。