目录
Problem A. balloon
题目描述
Xiaoxiang has nn children and mm balloons.
After class this day, my friends are going to grab these balloons. Each balloon has a certain height on the wall. Only when the children jump up, the height that their hands can reach is greater than or equal to the height of the balloon, and the children can pick up the balloon.
For the sake of fairness, the teacher asked the children who jumped low to pick them first, and the children who jumped high to pick them later.
Children are very greedy, and every child will take off all the balloons he can pick when picking balloons.
Coincidentally, the children can reach different heights when they jump up, so that there will be no disputes among children with the same height after jumping up.
输入描述:
The first line contains two integers n, mn,m , which respectively represent the number of children and the number of balloons.
The second line contains nn positive integers a_1, a_2, …, a_na1,a2,…,an.
The third line contains mm positive integers h_1, h_2, …, h_mh1,h2,…,hm
1 \leq n, m \leq 10^51≤n,m≤105 1 \leq a_i, h_i \leq 10^91≤ai,hi≤109
输出描述:
Output a total of nn lines, each line is an integer, where the ii line indicates the number of balloons picked by the ii th child.
示例1
输入
复制
5 6 3 7 9 6 4 1 2 3 4 5 6
输出
复制
3 0 0 2 1
示例2
输入
复制
10 10 1 2 3 4 5 6 7 8 9 10 3 1 4 6 7 8 9 9 4 12
输出
复制
1 0 1 2 0 1 1 1 2 0
思路：
本题直接写会超时，可以将b数组进行排序，用一个pre指针记录上一个高度的人拿到的气球的位置；
import java.util.*;
import java.io.*;
class r{
int idx,num,h;
}
public class Main {
static class FastScanner{
BufferedReader br;
StringTokenizer st;
public FastScanner(InputStream in){
br=new BufferedReader(new InputStreamReader(in),16834);
eat("");
}
private void eat(String s) {
// TODO Auto-generated method stub
st=new StringTokenizer(s);
}
public String nextLine() {
try {
return br.readLine();
}catch(IOException e) {
return null;
}
}
public boolean hasNext() {
while(!st.hasMoreTokens()) {
String s=nextLine();
if(s==null)return false;
eat(s);
}
return true;
}
public String next() {
hasNext();
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
static FastScanner cin=new FastScanner(System.in);
static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static void main(String[] args) {
// TODO Auto-generated method stub
int n=cin.nextInt(),m=cin.nextInt();
r a[]=new r[n];
int b[]=new int[m];
for(int i=0;i<n;i++) {
a[i]=new r();
a[i].h=cin.nextInt();
a[i].idx=i;
}
for(int i=0;i<m;i++)b[i]=cin.nextInt();
Arrays.sort(b);
Arrays.sort(a,new Comparator<r>() {
public int compare(r o1,r o2) {
return o1.h-o2.h;
}
});
int pre=0;
for(int i=0;i<n;i++) {
int j=0;
for(j=pre;j<m;j++) {
if(b[j]<=a[i].h) {
a[i].num++;
}else {
break;
}
}
pre=j;
if(pre==m)break;
}
Arrays.sort(a,new Comparator<r>() {
public int compare(r o1,r o2) {
return o1.idx-o2.idx;
}
});
for(int i=0;i<n;i++) {
out.println(a[i].num);
}
out.flush();
}
}
Problem B. sophistry
链接：
登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
In Xiao K’s QQ group, Xiao T always gets weird and weird.
Xiao T will speak in the group for nnn days, and xiao K has an anger value of mmm.
Xiao T has an ability value every day, and the ability value on day iii is aia_iai. Every day, Xiao T will choose whether to laugh at Xiao K. If Xiao T chooses to laugh at Xiao K on day iii, Xiao K will be hurt by aia_iai from Xiao T. On this basis, if Xiao T’s ability value aia_iai exceeds Xiao K’s anger value mmm, Xiao K will be furious and ban Xiao T for ddd days. That is to say, in i+1,i+2,…,min(i+d,n)i+1, i+2, …, \min(i+d, n)i+1,i+2,…,min(i+d,n) days, Xiao T will be banned.
Now, Xiao T wants to maximize the damage to Xiao K, but Xiao T is too bad to solve this problem, so he found you. hope you can help him solve this problem. You only need to find out the maximum damage caused by Xiao T to Xiao K.
输入描述:
The first line contains three positive integers n,d,m.n, d, m.n,d,m.
The second line contains nnn positive integers a1,a2,…,ana_1, a_2, …, a_na1,a2,…,an。
1≤n≤1051 \leq n \leq 10^51≤n≤105，1≤m,ai≤1091 \leq m, a_i \leq 10^91≤m,ai≤109 ，1≤d<n1 \leq d < n1≤d<n
输出描述:
Only one number per line is output, indicating the biggest damage caused by Xiao T to Xiao K。
示例1
输入
复制5 2 11 8 10 15 23 5
5 2 11 8 10 15 23 5
输出
复制41
41
示例2
输入
复制20 2 16 20 5 8 2 18 16 2 16 16 1 5 16 2 13 6 16 4 17 21 7
20 2 16 20 5 8 2 18 16 2 16 16 1 5 16 2 13 6 16 4 17 21 7
输出
复制156
156
思路：
从后往前进行遍历，分为两种情况：
1.当前点超过了m：如果a[i]+b[i+d+1]>b[i+1],b[i]=a[i]+b[i+d+1],否则b[i]=b[i+1];(当前i+d+1>=n,特判一下)
2.当前点<=m:b[i]=b[i+1]+a[i];
import java.util.*;
import java.io.*;
public class Main {
static class FastScanner{
BufferedReader br;
StringTokenizer st;
public FastScanner(InputStream in) {
br=new BufferedReader(new InputStreamReader(in),16834);
eat("");
}
private void eat(String s) {
// TODO Auto-generated method stub
st=new StringTokenizer(s);
}
public String nextLine() {
try {
return br.readLine();
}catch(IOException e) {
return null;
}
}
public boolean hasNext() {
while(!st.hasMoreTokens()) {
String s=nextLine();
if(s==null)return false;
eat(s);
}
return true;
}
public String next() {
hasNext();
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public Double nextDouble() {
return Double.parseDouble(next());
}
}
static FastScanner cin=new FastScanner(System.in);
static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) {
int n=cin.nextInt(),d=cin.nextInt(),m=cin.nextInt();
int a[]=new int[n+1];
long b[]=new long[n+1];
long s=0;
for(int i=0;i<n;i++)a[i]=cin.nextInt();
for(int i=n-1;i>=0;i--) {
if(a[i]<=m) {
b[i]=a[i]+b[i+1];
}
else {
if(i+d+1<=n-1) {
if(a[i]+b[i+d+1]>b[i+1]) {
b[i]=a[i]+b[i+d+1];
}else b[i]=b[i+1];
}else {
if(a[i]>b[i+1])b[i]=a[i];
else b[i]=b[i+1];
}
}
}
out.println(b[0]);
out.flush();
}
}
Proble***xsum
链接：
登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
Give you nnn numbers aia_iai, define S(l,r)=∑i=lrai(1≤l≤r≤n)S_{(l, r)}=\sum\limits_{i=l}^r a_i (1 \leq l \leq r \leq n)S(l,r)=i=l∑rai(1≤l≤r≤n), obviously There are n×(n+1)2S\dfrac{n \times (n+ 1)}{2} S2n×(n+1)S，the person who made the question wants to know the top wSw SwS.
输入描述:
The first line is two integers n,wn, wn,w
The number of nnn in the second line, the number of iii is ai.a_i.ai.
0≤ai≤109,0≤w≤min(n×(n+1)2,105),0≤n≤1050 \leq a_i \leq 10^9 ,0 \leq w \leq \min\left(\dfrac{n \times (n + 1)}{2}, 10^5\right),0 \leq n \leq 10^50≤ai≤109,0≤w≤min(2n×(n+1),105),0≤n≤105
输出描述:
Output the number of www, which represents the answer, separated by spaces.
示例1
输入
6 8 1 1 4 5 1 4
输出
16 15 14 12 11 11 10 10
示例2
输入
7 8 1 9 1 9 8 1 0
输出
29 29 28 28 28 27 20 19
思路：
用优先队列存当前最大值，左右端点。mp记录已经出现过的区间，防止重复入队。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<pair<int,int>,bool>mp;
const int N=100010;
struct node{
int l,r;
ll sum;
friend bool operator< (node o1,node o2){
return o1.sum<o2.sum;
}
};
int main(){
int n,w;
cin>>n>>w;
int a[n];
ll sum=0;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
priority_queue<node> q;
q.push({0,n-1,sum});
while(w>0){
node t=q.top();
q.pop();
w--;
cout<<t.sum<<" ";
int l=t.l,r=t.r;
if(l<r){
if(!mp[{l+1,r}]){
mp[{l+1,r}]=true;
q.push({l+1,r,t.sum-a[l]});
}
if(!mp[{l,r-1}]){
mp[{l,r-1}]=true;
q.push({l,r-1,t.sum-a[r]});
}
}
}
return 0;
}
Problem E. array
链接：
登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
Given two integer arrays a,ba, ba,b，Bob wants to know the array ccc。
ci=max0≤j<n{aj+b(i−j+n) mod n}c_i = \max_{0 \leq j <n}\{a_j + b_{(i−j+n)\bmod n}\}ci=max0≤j<n{aj+b(i−j+n)modn}
输入描述:
The first line is a positive integer nnn
The second line is nnn integers a0,a1,⋯ ,an−1.a_0, a_1, \cdots, a_{n−1}.a0,a1,⋯,an−1.
The third line is nnn integers b0,b1,⋯ ,bn−1b_0, b_1, \cdots, b_{n−1}b0,b1,⋯,bn−1
0≤ai,bi≤5000,∑ai≤5000,∑bi≤5000,n≤2×1050 \leq a_i,b_i \leq 5000,\sum{a_i \leq 5000},\sum{b_i \leq 5000},n \leq 2 \times 10^50≤ai,bi≤5000,∑ai≤5000,∑bi≤5000,n≤2×105
输出描述:
Output a line of nnn integers c0,c1,⋯ ,cn−1c_0, c_1, \cdots, c_{n−1}c0,c1,⋯,cn−1
示例1
输入
复制5 3 2 4 7 5 8 9 6 1 0
5 3 2 4 7 5 8 9 6 1 0
输出
复制14 12 12 15 16
14 12 12 15 16
思路
：
由此可知，不管n多大，非零数最多只有5000个，然后暴力求解；并且由题意可得 i=(j+(i-j+n)%n)%n;
import java.util.*;
import java.io.*;
public class Main {
static class FastScanner{
BufferedReader br;
StringTokenizer st;
public FastScanner(InputStream in) {
br=new BufferedReader(new InputStreamReader(in),16834);
eat("");
}
private void eat(String s) {
// TODO Auto-generated method stub
st=new StringTokenizer(s);
}
public String nextLine() {
try {
return br.readLine();
}catch(IOException e) {
return null;
}
}
public boolean hasNext() {
while(!st.hasMoreTokens()) {
String s=nextLine();
if(s==null)return false;
eat(s);
}
return true;
}
public String next() {
hasNext();
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public Double nextDouble() {
return Double.parseDouble(next());
}
}
static FastScanner cin=new FastScanner(System.in);
static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
static int N=5010;
static int cnt1[]=new int[N];//记录a中非零数的位置
static int cnt2[]=new int[N];//记录b中非零数的位置
public static void main(String[] args) {
int n=cin.nextInt();
int a[]=new int[n],b[]=new int[n];
int c[]=new int[n];
int max=-1,len1=0,len2=0;//max用来存a,b数组的最大值,len1表示a组中非零的个数，len1表示b组中非零的个数
for(int i=0;i<n;i++) {
a[i]=cin.nextInt();
max=Math.max(max,a[i]);
if(a[i]!=0)cnt1[len1++]=i;
}
for(int i=0;i<n;i++) {
b[i]=cin.nextInt();
max=Math.max(b[i],max);
if(b[i]!=0)cnt2[len2++]=i;
}
for(int i=0;i<len1;i++) {
for(int j=0;j<len2;j++) {
//cnt1[i]代表j,cnt2[j]代表(i-j+n)%n;
int t=(cnt1[i]+cnt2[j])%n;
c[t]=Math.max(c[t],a[cnt1[i]]+b[cnt2[j]]);
}
}
for(int i=0;i<n;i++) {
c[i]=Math.max(c[i], max);
out.print(c[i]+" ");
}
out.flush();
}
}