[욕심] hdu3979 몬스터.
Monster
http://acm.hdu.edu.cn/showproblem.php?pid=3979
Problem Description
One day, v11 encounters a group of monsters in a foreast. In order to defend the homeland, V11 picks up his weapon and fights!
All the monsters attack v11 at the same time. Every enemy has its HP, and attack value ATK. In this problem, v11 has his ATK and infinite HP. The damage (also means reduction for HP) is exactly the ATK the attacker has. For example, if v11's ATK is 13 and the monster's HP is 27, then after v11's attack, the monster's HP become 27 - 13 = 14 and vice versa.
v11 and the monsters attack each other at the same time and they could only attack one time per second. When the monster's HP is less or equal to 0 , we think this monster was killed, and obviously it would not attack any more. For example, v11's ATK is 10 and a monster's HP is 5, v11 attacks and then the monster is killed! However, a monster whose HP is 15 will be killed after v11 attack for two times. v11 will never stop until all the monsters are killed ! He wants to minimum the HP reduction for the fight! Please note that if in some second, some monster will soon be killed , the monster's attack will works too.
Input
The first line is one integer T indicates the number of the test cases. (T <=100)
Then for each case, The first line have two integers n (0
Output
Output one line.
First output “Case #idx: ”, here idx is the case number count from 1. Then output the minimum HP reduction for v11 if he arrange his attack order optimal .
Sample Input
2
3 1
1 10
1 20
1 40
1 10
7 3
Sample Output
Case #1: 110
Case #2: 3
욕심은 우선 모든 몬스터를 죽이는 데 필요한 시간 t를 계산한 다음에 몬스터의 피해와 살해에 필요한 비율에 따라 순서를 정한다. 물론 비율이 높은 몬스터를 우선적으로 죽인다.
롱롱을 사용해야 합니다.#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
struct node
{
LL hp;
LL g;
LL t;
}monster[10005];
bool cmp(const struct node &a,const struct node &b)
{
return (double)a.g/a.t>(double)b.g/b.t;
}
int main()
{
int T,n,m;
scanf("%d",&T);
for(int tt=1;tt<=T;++tt)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
scanf("%I64d%I64d",&monster[i].hp,&monster[i].g);
monster[i].t=(monster[i].hp/m+((monster[i].hp%m)?1:0));
}
sort(monster,monster+n,cmp);
LL reduction=0,t=0;
for(int i=0;i<n;++i)
{
t+=monster[i].t;
reduction+=(t*monster[i].g);
}
printf("Case #%d: %I64d
",tt,reduction);
}
return 0;
}
출처:http://blog.csdn.net/acm_ted/article/details/7773137
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스
은 접근자 메서드가 있는 속성 모음입니다.
클래스를 명시적으로 작성할 필요 없이.
Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다.
각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
Problem Description
One day, v11 encounters a group of monsters in a foreast. In order to defend the homeland, V11 picks up his weapon and fights!
All the monsters attack v11 at the same time. Every enemy has its HP, and attack value ATK. In this problem, v11 has his ATK and infinite HP. The damage (also means reduction for HP) is exactly the ATK the attacker has. For example, if v11's ATK is 13 and the monster's HP is 27, then after v11's attack, the monster's HP become 27 - 13 = 14 and vice versa.
v11 and the monsters attack each other at the same time and they could only attack one time per second. When the monster's HP is less or equal to 0 , we think this monster was killed, and obviously it would not attack any more. For example, v11's ATK is 10 and a monster's HP is 5, v11 attacks and then the monster is killed! However, a monster whose HP is 15 will be killed after v11 attack for two times. v11 will never stop until all the monsters are killed ! He wants to minimum the HP reduction for the fight! Please note that if in some second, some monster will soon be killed , the monster's attack will works too.
Input
The first line is one integer T indicates the number of the test cases. (T <=100)
Then for each case, The first line have two integers n (0
Output
Output one line.
First output “Case #idx: ”, here idx is the case number count from 1. Then output the minimum HP reduction for v11 if he arrange his attack order optimal .
Sample Input
2
3 1
1 10
1 20
1 40
1 10
7 3
Sample Output
Case #1: 110
Case #2: 3
욕심은 우선 모든 몬스터를 죽이는 데 필요한 시간 t를 계산한 다음에 몬스터의 피해와 살해에 필요한 비율에 따라 순서를 정한다. 물론 비율이 높은 몬스터를 우선적으로 죽인다.
롱롱을 사용해야 합니다.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
struct node
{
LL hp;
LL g;
LL t;
}monster[10005];
bool cmp(const struct node &a,const struct node &b)
{
return (double)a.g/a.t>(double)b.g/b.t;
}
int main()
{
int T,n,m;
scanf("%d",&T);
for(int tt=1;tt<=T;++tt)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
scanf("%I64d%I64d",&monster[i].hp,&monster[i].g);
monster[i].t=(monster[i].hp/m+((monster[i].hp%m)?1:0));
}
sort(monster,monster+n,cmp);
LL reduction=0,t=0;
for(int i=0;i<n;++i)
{
t+=monster[i].t;
reduction+=(t*monster[i].g);
}
printf("Case #%d: %I64d
",tt,reduction);
}
return 0;
}
출처:http://blog.csdn.net/acm_ted/article/details/7773137
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.