CodeForces 23C Oranges and Apples(간단한 문제)
2395 단어 codeforces아이디어
제목의 의미
n(n<=1e5)을 입력하면 다음에 2*n-1개의 상자가 있고, 상자마다 a개의 귤과 b개의 사과가 있습니다. 지금 2*n-1개의 상자 중에서 n개의 상자를 선택하라고 합니다.
이 n개 상자 안의 귤 총수는 귤 총수의 절반보다 작지 않고, 사과 총수는 사과 총수의 절반보다 작지 않게 하다
문제풀이 방법
2*n-1 상자를 귤의 수량에 따라
작은 것부터 큰 것까지 정렬한 다음에 아래에 홀수(아래 것은 1부터)로 표시된 상자에 대해 만약 이 상자의 사과 수가 요구에 부합된다면
결과는 이 아래에 홀수로 표시된 예이다. 그렇지 않으면 결과는 짝수로 표시된 상자에 마지막 상자를 더한다
7개의 상자가 있다고 가정하면(a는 귤, b는 사과, 수마는 귤
총수
a1+a3+a5+a7은 a2+a4+a6보다 크니까 (a7>=a6a5>=a4a3>=a2a1>=0) 즉 a1+a3+a5+a7>=Suma/2
그렇다면 b1+b3+b5+b7>=Sumb/2는 분명히 1357(귤과 사과 모두 조건 충족)
그러나 이 상자들이 조건 즉 b1+b3+b5+b7
사과
b1+b2+b3+b4+b5+b6+b7 = Sumb
하면, 만약, 만약...
b1+b3+b5+b7
(b2+b4+b6)>Sumb/2, 즉 a2+a4+a6+a7>Sumb/2
사과도 만족해요.
코드 참고. - 궁금한 거 있으면 댓글로 남겨주시면 빨리 답장해드릴게요.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e5*2 + 10;
struct P{
int a, b, pos;
}p[MAXN];
bool cmp(const P & a, const P & b) {
return a.a < b.a;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n;
LL suma = 0, sumb = 0;
scanf("%d", &n);
for( int i=1; i<=2*n-1; i++ ) {
scanf("%d%d", &p[i].a, &p[i].b);
suma += p[i].a;
sumb += p[i].b;
p[i].pos = i;
}
sort(p+1, p + 2*n-1+1, cmp);
LL t1 = 0, t0 = 0;
for( int i=1; i<=2*n-1; i++ ) {
if(i&1) t1 += p[i].b;
else t0 += p[i].b;
}
if(t1 * 2 >= sumb) {
printf("YES
");
for( int i=1; i<=2*n-1; i++ ) {
if(i&1) printf("%d ", p[i].pos);
}
printf("
");
}
else if((t0 + p[2*n-1].b)*2>=sumb) {
printf("YES
");
for( int i=1; i<=2*n-1; i++ ) {
if(i%2==0) printf("%d ", p[i].pos);
}
printf("%d
", p[2*n-1].pos);
}
else printf("NO
");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
