[vivo 2019 년] 알고리즘 강 필 시험 문제
4274 단어 회사 필기시험 문제
작은 v 는 회사 에서 게임 운영 을 맡 고 있 으 며, 오늘 새로 출시 하 는 게임 '점프' 를 신청 받 았 다.많은 게이머 들 에 게 제공 되 는 게임 이 모두 고 품질 임 을 확보 하기 위해 운영 절차 에 따라 작은 v 는 반드시 새로운 게임 에 대해 전방위 적 으로 체험 과 평 가 를 해 야 한다.이 게임 의 규칙 은 다음 과 같다. n 개의 상자 가 한 줄 로 되 어 있 고 각 상자 위 에 숫자 a [i] 가 있 으 며 이 상자 에 있 는 사람 이 최대 오른쪽으로 a [i] 상 자 를 이동 할 수 있다 는 것 을 나타 낸다. (예 를 들 어 현재 상자 에 있 는 숫자 는 3 이면 한 번 에 오른쪽으로 1 개의 상자, 2 개의 상자 또는 3 개의 상자).지금 작은 v 는 왼쪽 첫 번 째 상자 에서 게임 을 체험 하기 시 작 했 습 니 다. 적어도 몇 번 은 이동 해 야 마지막 상자 에 도착 할 수 있 습 니까?
입력 설명:
입력: 22304 는 현재 5 개의 상자 가 있 음 을 나타 내 며, 위의 숫자 는 각각 2, 2, 3, 0, 4 이다.
출력 설명: 출력: 2
작은 v 는 두 가지 점프 방법 이 있다.
점프 법 1: 상자 1 - 상자 2 - 상자 3 - 상자 4 - 상자 5, 총 3 대
점프 법 2: 상자 1 - 상자 3 - 상자 5, 총 2 대
점프 2 의 절차 수량 이 가장 적 기 때문에 출력 최소 걸음 수: 2.
입력:
2 2 3 0 4
출력:
2
핵심 코드:
int jump(int a[], int n) {
int steps = 0;
int start = 0;
int end = 0;
while(end < n - 1)
{
int max_pos = 0;
for(int i = start; i <= end; ++i)
max_pos = max(max_pos, i + a[i]);
start = end + 1;
end = max_pos;
++steps;
}
return steps;
}제목 설명:
올해 7 월 에 vivo 는 새로 입사 한 대학생 을 맞이 했 기 때문에 지금 은 모든 새로운 동료 에 게 일자 리 를 배정 해 야 한다.인적자원 부 동료 인 작은 v 는 모든 사람 에 게 순 서 를 매기 고 최종 작업 번 호 를 배정 하 는 방법 을 설계 했다. 구체 적 인 규칙 은 N (N < 100000) 개인 을 한 줄 로 세우 고 첫 번 째 사람 부터 번 호 를 알 리 는 것 이다. 만약 에 번호 가 M 의 배수 라면 배열 하고 팀 의 끝 에 보고 한 후에 팀 으로 돌아 가 계속 보고 하고 모든 사람 이 대열 에 나 갈 때 까지 한다.마지막 으로 열 거 된 순서에 따라 모든 사람 에 게 순서대로 노동 번 호 를 분배 한다.자신 이 잘 하 는 프로 그래 밍 언어 를 사용 하여 작은 v 가 이 방법 을 실현 하도록 도와 주세요.
입력 설명:
두 개의 정수, 빈 칸 구분, 첫 번 째 대표 인원수 N, 두 번 째 대표 M 을 입력 하 십시오.
출력 설명:
int 배열 을 출력 합 니 다. 모든 데 이 터 는 원래 대기 열 에 있 던 위 치 를 빈 칸 으로 구분 하여 열 순 서 를 표시 합 니 다.
입력:
6 3
출력:
3 6 4 2 5 1
이 문 제 는 간단 한 조세 프 링 입 니 다.
핵심 코드:
void loop(int n,int M)
{
int a[n],m=0,number=0;
int i,j;
for(j=0;j0)
{
m++;
if(m==M)
{
if(d >= 1)
printf(" %d",a[i]);
else
printf("%d", a[i]);
d++;
a[i]=0;
m=0;
number++;
if(number==n)
{
break;
}
}
}
if(i==(n-1))
{
i=-1;
}
}
cout << endl;
} 제목 설명:
작은 v 최근 에 광산 을 파 는 게임 을 하고 있 습 니 다. 이 게임 은 다음 과 같이 소개 합 니 다. 1. 매번 여러 개의 광석 을 파 낼 수 있 고 모든 광석 의 무게 가 다 릅 니 다. 광산 을 파 는 것 이 끝 난 후에 균형 광 차 를 통 해 산 을 내 려 가 야 합 니 다. 2. 균형 광 차 는 좌우 2 개의 칸 이 있 고 중간 에 1 개의 바퀴 만 도 로 를 따라 산 아래로 미 끄 러 지고 광 차 는 2 개의 칸 의 무게 가 똑 같 으 며 광석 의 수량 차이 가 1 개 를 초과 하지 않 는 상황 에서 만 광석 을 성공 적 으로 운송 할 수 있 으 며 그렇지 않 으 면 커 브 를 돌 때 옆으로 넘 어 질 수 있다.작은 v 가 n (n < 100) 개의 광석 을 파 냈 다 고 가정 하면 모든 광석 의 무게 가 100 을 초과 하지 않 고 n 개의 광석 을 한꺼번에 운송 하기 위해 광차 의 객차 의 무게 가 다 르 면 배합 분동 을 구 매 해 야 한다.작은 v 는 매번 적어도 몇 무게 의 분동 을 구 매해 야 합 니까?(차간 이 이 광석 과 분동 을 충분히 내 려 놓 을 수 있다 고 가정 하고 분동 의 무 게 는 선택 할 수 있다)
입력 설명:
n 개의 정 수 를 입력 하여 모든 광석 의 무 게 를 표시 하 다.
출력 설명:
정 수 를 출력 하여 최소 구 매 해 야 할 분동 의 무 게 를 표시 하 다.
입력:
3 7 4 11 8 10
출력:
1
설명:
작은 v 는 무게 3, 7, 11 의 광석 을 왼쪽 칸 에 놓 고 무게 4, 8, 10 을 오른쪽 칸 에 놓 은 다음 에 무게 가 1 인 저울추 를 사서 왼쪽 칸 에 놓 을 수 있다.
문제 풀이: 사실은 n 개 수 를 반 으로 나 누 어 절대 치 차 이 를 작 게 할 수 있 습 니 다. 우 리 는 01 가방 으로 바 꾸 어 할 수 있 습 니 다.
이 문 제 는 당시 80% 차이 가 나 지 않 았 습 니 다. 이 유 를 알 지 못 했 습 니 다. 오늘 문 제 를 발췌 할 때 문 제 는 광석 의 수량 차이 가 최대 1 이라는 것 을 알 게 되 었 습 니 다. 울 음 을 터 뜨 렸 습 니 다. 지금 은 제출 한 코드 를 붙 였 습 니 다. 정확 한 것 은 나중에 고치 세 요!!!
코드:
void loop(int n, int weight[])
{
int Sum = 0, sum;
int dp[10009];
for(int i = 0; i < n; i++)
Sum += weight[i];
sum = Sum / 2;
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; i++)
for(int v = sum; v >= weight[i]; v--)
dp[v] = max(dp[v], dp[v - weight[i]] + weight[i]);
Sum -= dp[sum];
// cout << dp[sum] << endl;
// cout << Sum << endl;
if(Sum > dp[sum])
cout << Sum - dp[sum] << endl;
else
cout << dp[sum] - Sum << endl;
}좋은 웹페이지 즐겨찾기
