욕심 알고리즘
이 문 제 는 최소한 몇 점 을 깎 아야 하 는 지 를 계산 하려 면 마지막 시간 전에 가장 많은 감점 을 받 은 숙제 를 먼저 배정 해 야 한 다 는 것 이다.벌점 이 똑 같이 많 으 면 시간 을 비교적 촉박 하 게 먼저 배정 해 야 한다.그래서 먼저 감점 의 높낮이 에 따라 높 은 것 에서 낮은 것 으로 순 위 를 매 깁 니 다.만약 에 두 과목 의 감점 이 같 으 면 그들의 종료 시간 에 따라 낮은 것 에서 높 은 것 으로 순 위 를 매 깁 니 다!그리고 준비 하면 돼!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1000
int f[N+5];
struct T
{
int deadline;
int score;
}homework[N+5];
int cmp(const void*a,const void*b)
{
if((*(struct T*)a).score!=(*(struct T*)b).score)
return (*(struct T*)b).score-(*(struct T*)a).score;
else
return (*(struct T*)a).deadline-(*(struct T*)b).deadline;
}
int main()
{
int C,n,i,j,sum;
scanf("%d",&C);
while(C--)
{
memset(f,0,sizeof(f));
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&homework[i].deadline);
for(i=0;i<n;i++)
scanf("%d",&homework[i].score);
qsort(homework,n,sizeof(homework[0]),cmp);
for(i=0,sum=0;i<n;i++)
{
for(j=homework[i].deadline;j>0;j--) //
{
if(f[j]==0)
{
f[j]=1;break;
}
}
if(j==0) // ，
sum+=homework[i].score;
}
printf("%d
",sum);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
