9 도 OJ 1371 (정렬) 1372 (DP) 1373 (통계) 1374 (통계) 1375 (통계)
http://ac.jobdu.com/problem.php?pid=1371
제목
n 개의 정 수 를 입력 하여 그 중에서 가장 작은 K 개 수 를 찾 아 라.
사고의 방향
정렬 하고 출력 합 니 다.
코드
#include<stdio.h>
#include<algorithm>
#define N 200005
using namespace std;
int main()
{
int n,k;
int i;
int a[N];
while(scanf("%d%d",&n,&k)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(i=0;i<k-1;i++)
{
printf("%d ",a[i]);
}
printf("%d
",a[k-1]);
}
return 0;
}
/**************************************************************
Problem: 1371
User: liangrx06
Language: C++
Result: Accepted
Time:860 ms
Memory:1728 kb
****************************************************************/
1372: 최대 하위 벡터 와
http://ac.jobdu.com/problem.php?pid=1372
제목
벡터 에서 연속 서브 벡터 의 최대 화 를 구 하 는 동시에 이 서브 벡터 의 첫 번 째 요소 의 아래 표 와 마지막 요소 의 아래 표 시 를 구 합 니 다.여러 개의 키 벡터 가 존재 한다 면 출력 시작 요소 아래 표 시 된 것 이 가장 작은 것 입 니 다.
사고의 방향
기본 DP 문제.제 코드 는 DP 를 배우 기 전에 쓴 것 입 니 다. 복잡 도와 DP 는 모두 O (N) 입 니 다.
코드
#include <stdio.h>
int main(void)
{
int n;
long long a[1000000];
int i;
long long best, bestTmp;
long long bestL, bestR, bestTmpL, bestTmpR;
while (scanf("%d", &n) != EOF)
{
if (n == 0)
break;
for (i=0; i<n; i++)
scanf("%lld", &a[i]);
best = a[0];
bestL = bestR = 0;
bestTmp = a[0];
bestTmpL = bestTmpR = 0;
for (i=1; i<n; i++)
{
if (bestTmp < 0)
{
bestTmp = a[i];
bestTmpL = bestTmpR = i;
}
else
{
bestTmp += a[i];
bestTmpR = i;
}
if (bestTmp > best)
{
best = bestTmp;
bestL = bestTmpL;
bestR = bestTmpR;
}
}
printf("%lld %lld %lld
", best, bestL, bestR);
}
return 0;
}
/************************************************************** Problem: 1372 User: liangrx06 Language: C Result: Accepted Time:470 ms Memory:8652 kb ****************************************************************/
1373: 정수 중 1 이 나타 난 횟수
http://ac.jobdu.com/problem.php?pid=1373
제목
a 와 b 사이 의 숫자 1 이 나타 나 는 횟수 를 출력 합 니 다.
사고의 방향
각각 1 - (a - 1) 과 1 - b 사이 에 나타 난 횟수 를 구하 고 둘 은 줄 이려 고 한다.
코드
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int count(char *s, int a)
{
int n = strlen(s);
int i;
int res = 0;
int pow10i = 1;
int si;
for (i=0; i<n; i++)
{
res += a/(pow10i*10)*pow10i;
si = n-1-i;
if (s[si] > '1')
res += pow10i;
if (s[si] == '1')
res += a%pow10i + 1;
//printf("i=%d, a=%d, pow10i=%d, res=%d
", i, a, pow10i, res);
pow10i *= 10;
}
return res;
}
int main()
{
int i;
char sa[11], sb[11];
int a, b;
while(scanf("%s%s", sa, sb) != EOF)
{
a = atoi(sa);
b = atoi(sb);
if (a > b)
{
int tmp = a;
a = b;
b = tmp;
char stmp[11];
strcpy(stmp, sa);
strcpy(sa, sb);
strcpy(sb, stmp);
}
int counta = 0;
int tmpa = a;
for (i=0; i<strlen(sa); i++)
{
if (tmpa%10 == 1)
counta ++;
tmpa /= 10;
}
int count0toa = count(sa, a);
int count0tob = count(sb, b);
printf("%d
", count0tob - count0toa + counta);
}
return 0;
}
/************************************************************** Problem: 1373 User: liangrx06 Language: C Result: Accepted Time:0 ms Memory:912 kb ****************************************************************/
1374: 모든 직원 연령 순위
http://ac.jobdu.com/problem.php?pid=1374
제목
회사 내 직원 연령 서열.
사고의 방향
이 문제 의 특징 은 age 수치 범위 가 (1 < = age < = 99) 이 고 한 배열 로 모든 age 의 출현 횟수 를 통계 할 수 있 습 니 다.알고리즘 복잡 도 O (N).빨리 줄 서. 시간 초과 될 것 같 애.
코드
#include <stdio.h>
#include <string.h>
#define N 1000000
int main()
{
int i, j, n;
int a[N];
int count[100];
while(scanf("%d", &n) != EOF)
{
memset(count, 0, sizeof(count));
for (i=0; i<n; i++)
{
scanf("%d", &a[i]);
count[a[i]] ++;
}
for (i=1; i<100; i++)
{
for (j=0; j<count[i]; j++)
printf("%d ", i);
}
printf("
");
}
return 0;
}
/**************************************************************
Problem: 1374
User: liangrx06
Language: C
Result: Accepted
Time:790 ms
Memory:4748 kb
****************************************************************/
1375: 천 보 의 완벽 주의
http://ac.jobdu.com/problem.php?pid=1375
제목
하나의 정수 서열 d1, d2, d3. dn 에 대해 당신 은 적어도 그 중의 몇 개 수 를 바 꿔 야 그들 을 1 에서 N 까지 의 배열 로 바 꿀 수 있 습 니까?
사고의 방향
통계 1 - N 에서 나타 나 지 않 은 개수 가 답 이다.
코드
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 100000
#define M 100
int main()
{
int i, n;
int a[N], b[N+1];
char s[M+1];
while(scanf("%d", &n) != EOF)
{
memset(b, 0, sizeof(b));
for (i=0; i<n; i++)
{
scanf("%s", s);
if (strlen(s) > 9)
a[i] = 0;
else
a[i] = atoi(s);
if (a[i] <= n && a[i] >= 1)
b[a[i]]++;
}
int count = 0;
for (i=1; i<=n; i++)
{
if (b[i] > 0)
count ++;
}
printf("%d
", n-count);
}
return 0;
}
/************************************************************** Problem: 1375 User: liangrx06 Language: C Result: Accepted Time:170 ms Memory:1232 kb ****************************************************************/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
엑셀 VBA에서 동적 계획법으로 DNA 서열의 정렬 만들기 Needleman-Wunsch 알고리즘 구현이 기사는 DNA 서열의 정렬을 반환하는 엑셀 함수에 대한 기사입니다. 그렇다면 다음과 같은 정렬을 반환하는 함수입니다. 두 개의 행렬을 준비합니다. 정렬하고 싶은 2개의 DNA 서열의 길이를 m과 n으로 하면, 세...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.