POJ 3262 꽃의 욕심 을 보호

제목 의 뜻 은 매우 간단 하 다.
n 마리 의 소 가 FJ 의 화원 에서 마구 먹는다.
그래서 FJ 는 그들 을 외양간 으로 돌려 보 내야 한다.
모든 소 는 쫓 겨 나 기 전에 매 초 에 디 개의 꽃 을 먹는다.FJ 로 돌려 보 내 는데 걸 리 는 시간 은 Ti 야.쫓 겨 나 는 동안 소 를 함부로 먹 으 면 안 돼 요.
그럼 사실 제 첫 느낌 은 비율 과 관련 이 있다 는 거 예요.
그리고 간략하게 증 명 했 습 니 다.
가설 서열 은 모두 이원 조 로 구성 되 고 이원 조 는 D 와 T 로 구성 된다 면 한 서열 에 인접 한 두 마리 의 소 는 이렇다.
..........(a, b) ,(c, d)....................
하면, 만약, 만약...
새 시퀀스 로 변경
..........(c,d),(a,b).....................
그 전에 FJ 가 x 시간 이 걸 렸 다 고 가정 해 봐.
그러면 이 소 두 마 리 를 다 몰 고 나 면 피 해 는 각각...
x*b + (x + a ) * d
x*d +(x + c) * b
양자 택일
ad 받 기 - bc
만약 ad < bc 는 첫 번 째 서열 이 두 번 째 서열 보다 낫다
그럼 이게 비율 이 잖 아 요.
그러면 임의의 서열 에 대해 우 리 는 이런 인접 한 교환 을 통 해 서열 을 가장 좋 은 것 으로 만 들 수 있다.
그 러 니까 증명 완료.
12 년 금화 지구 어느 출석 문제 가 이 거 였 죠?당시 에 직접 추측 한 결론 도 증명 되 지 않 았 고 실제로 증명 하 는 것 도 간단 하 겠 지 요.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 111111
#define MAXM 222222
#define INF 1000000000
using namespace std;
struct node
{
    int x, y;
}a[MAXN];
int n;
bool cmp(node x, node y)
{
    return x.x * y.y < x.y * y.x;
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].x *= 2;
    }
    sort(a, a + n, cmp);
    long long ans = 0;
    long long sum = 0;
    for(int i = 0; i < n; i++)
    {
        ans += sum * (long long)a[i].y;
        sum += a[i].x;
    }
    printf("%I64d
", ans);
    return 0;
}
Flex 4.5 skin 피부 구성 응용
c 언어 학습 노트 정리 (15) - 비트 조작

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage