《 도전 프로 그래 밍 경 기 》 2.2.2 욕심 법 - 기타 POJ 3617 3069 3253 2393 1017 3040 1862 3262

POJ3617
Best Cow Line
제목
길이 가 N 인 문자열 S 를 지정 합 니 다. 길이 가 N 인 문자열 T 를 만 듭 니 다.처음에 T 는 빈 문자열 이 었 습 니 다. 그 다음 에 다음 과 같은 임 의 작업 을 반복 합 니 다. S 의 머리 (또는 꼬리) 에서 문 자 를 삭제 하고 T 의 꼬리 부분 목 표 는 사전 순 서 를 최대한 작은 문자열 T 로 구성 하 는 것 입 니 다.
사고의 방향
욕심 산법 은 S 의 시작 과 끝 에 있 는 작은 문 자 를 T 의 끝 에 계속 가 져 옵 니 다.그러나 S 의 시작 과 끝 문자 가 같은 경우 다음 문자 크기 를 비교 해 야 합 니 다. 이 는 다음 과 같은 알고리즘 으로 이 루어 집 니 다. 사전 순서에 따라 S 와 S 가 뒤 집 힌 문자열 S1 을 비교 하고 S 가 작 으 면 S 의 시작 에서 가 져 옵 니 다. 그렇지 않 으 면 끝 에서 가 져 옵 니 다.
코드

Source Code

Problem: 3617       User: liangrx06
Memory: 728K        Time: 47MS
Language: G++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define N 2000

int main(void)
{
    int n, i, j, k, ii, jj;
    char s[N+1], t[N+1];

    while (cin >> n)
    {
        for (i=0; i<n; i++) {
            getchar();
            scanf("%c", &s[i]);
        }
        s[i] = '\0';
        i = 0;
        j = n-1;
        k = 0;
        while (i <= j) {
            ii = i, jj = j;
            while (ii <= jj) {
                if (s[ii] != s[jj])
                    break;
                ii ++;
                jj --;
            }
            if (ii <= jj && s[ii] > s[jj]) {
                t[k++] = s[j];
                j --;
            }
            else {
                t[k++] = s[i];
                i ++;
            }
        }
        t[k] = '\0';
        for (i = 0; i < n; i++)
        {
            printf("%c", t[i]);
            if (i % 80 == 79) printf("
");
        }
        if (n % 80) printf("
");
    }

    return 0;
}

POJ3069
Saruman’s Army
제목
이 문 제 는 n 개의 점 을 주 고 가능 한 한 적은 점 을 표시 하여 n 개의 점 이 모두 표 시 된 점 좌우 로 R 을 초과 하지 않 는 구간 에 있 도록 하 는 것 이다.
사고의 방향
욕심 법 은 왼쪽 에서 오른쪽으로 선택한다.
코드

Source Code

Problem: 3069       User: liangrx06
Memory: 748K        Time: 125MS
Language: G++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define N 1000

int main(void)
{
    int r, n, i, j;
    int pos[N], res;

    while (cin >> r >> n) {
        if (r == -1 && n == -1)
            break;

        for (i=0; i<n; i++)
            cin >> pos[i];
        sort(pos, pos+n);

        res = 0;
        i = 0;
        while (i < n) {
            j = i+1;
            while (j < n && pos[j] - pos[i] <= r)
                j ++;
            j --;

            i = j+1;
            while (i < n && pos[i] - pos[j] <= r)
                i ++;
            res ++;
        }
        cout << res << endl;
    }

    return 0;
}

POJ3253
Fence Repair
제목
한 농부 가 널 빤 지 를 몇 개의 주어진 길이 의 작은 널빤지 로 만들어 야 한다. 톱 을 켤 때마다 일정한 비용 을 받 아야 한다. 이 비용 은 바로 현재 톱 을 자 르 는 이 널빤지 의 길이 이다.각 요구 하 는 작은 널빤지 의 길이 와 작은 널빤지 의 개수 n 을 정 하고 최소 비용 을 구한다.알림: 3585 를 예 로 들 면 한 없 이 긴 널빤지 에서 길이 가 21 인 널 빤 지 를 먼저 톱질 하고, 길이 가 21 인 널빤지 에서 길이 가 5 인 널 빤 지 를 21 인 널빤지 에서 톱질 하고, 길이 가 16 인 널빤지 에서 길이 가 8 인 널 빤 지 를 5 인 널빤지 에서 5 인 널빤지 로 톱질 하 는데 8 인 총 소비 = 21 + 5 + 8 = 34
사고의 방향
Huffman 사상 을 이용 하여 총 비용 을 최소 화 하려 면 매번 최소 길이 의 널빤지 두 개 만 선택 하고 이 '와' 를 총 비용 에 누적 하면 된다. 본 문 제 는 Huffman 사상 을 이용 하지만 Huffman Tree 로 직접 하면 시간 이 초과 되 어 우선 대열 로 할 수 있다.
코드

Source Code

Problem: 3253       User: liangrx06
Memory: 1184K       Time: 219MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

int main(void)
{
    int n, i;
    long long x, sum;
    multiset <long long> plank;

    while (cin >> n)
    {
        for (i=0; i<n; i++) {
            cin >> x;
            plank.insert(x);
        }

        sum = 0;
        while (plank.size() > 1)
        {
            x = *(plank.begin()) + *(++plank.begin());
            sum += x;
            plank.erase(plank.begin());
            plank.erase(plank.begin());
            plank.insert(x);
        }

        cout << sum << endl;
        plank.clear();
    }

    return 0;
}

POJ2393
Yogurt factory
제목
n 주, i 주: 외부 공급 yi, 생산 1 단위 원가 ci.만약 이번 주 에 생산 한 화물 이 이번 주 에 판매 되 지 않 는 다 면 저장 해 야 하고 1 단 위 는 일주일 에 s 를 저장 해 야 한다.n 주 납품 에 얼마 가 들 었 는 지 (원가 와 저장 비) 물 어보 세 요.
사고의 방향
욕심 이 나 면 우 리 는 minc 로 현재 의 최소 단 가 를 기록 한 다음 에 최소 단가 로 매입 합 니 다. 이 최소 단 가 는 현재 의 단가 이거 나 이전의 최소 단가 + 저장 비 입 니 다.minc 에서 교 체 된 값 은 이후 의 최소 단가 일 수 없습니다.현재 바 뀌 었 기 때문에, 동시에 + 몇 개의 s 를 올 린 후에 도 그것 은 현재 의 그 값 보다 클 것 입 니 다.
코드

Source Code

Problem: 2393       User: liangrx06
Memory: 132K        Time: 16MS
Language: C++       Result: Accepted
Source Code
#include<iostream>
using namespace std;

int main()
{
    int n, s, minc = 9999;
    scanf("%d %d", &n, &s);
    long long sum = 0;
    while(n --){
        int c, y;
        scanf("%d %d", &c, &y);
        if(c > minc + s)
            c = minc + s;
        minc = c;
        sum += c * y;
    }
    printf("%lld
", sum);
    return 0;
}

POJ1017
Packets
제목
문 제 는 한 공장 에서 제조 한 제품 의 모양 이 모두 직사각형 이 고 그들의 높이 는 모두 h 이 며 길이 와 너비 가 모두 같다 는 것 을 묘사 했다. 모두 6 개의 모델 이 있 는데 그들의 길 이 는 각각 1 * 1, 2 * 2, 3 * 3, 4 * 4, 5 * 5, 6 * 6 이다. 이런 제품 들 은 보통 6 * 6 * h 의 직사각형 소포 로 포장 한 후에 고객 에 게 우편 으로 보낸다.우편요금 이 매우 비 싸 기 때문에 공장 은 모든 주문 운송 시의 소포 수량 을 줄 이려 고 노력 해 야 한다.그들 은 그들 이 이 문 제 를 해결 하도록 도와 비용 을 절약 할 좋 은 절 차 를 필요 로 한다.지금 이 프로그램 은 네가 설계 해라.입력 데이터 입력 파일 은 몇 줄 을 포함 하고 각 줄 은 하나의 주문 서 를 대표 합 니 다.각 주문서 의 한 줄 은 여섯 개의 정 수 를 포함 하고 중간 은 빈 칸 으로 나 누 어 각각 1 * 1 에서 6 * 6 이라는 여섯 가지 제품 의 수량 이다.입력 파일 은 0 으로 구 성 된 6 줄 로 끝 납 니 다.출력 요 구 는 입력 한 마지막 줄 6 개 0 을 제외 하고 입력 파일 에 있 는 줄 마다 출력 파일 의 줄 에 대응 하고 줄 마다 정 수 를 출력 하 는 것 은 해당 하 는 주문 에 필요 한 최소 패키지 수 를 나타 낸다.입력 샘플 0 0 4 0 1 7 5 1 0 0 0 0 0 0 0 0 출력 샘플 2 1
사고의 방향
이 문 제 는 비교적 명확 하 게 묘사 되 었 습 니 다. 우 리 는 여기 서 입 출력 사례 만 설명 하 겠 습 니 다. 모두 두 조 의 유효 수입 이 있 습 니 다. 첫 번 째 조 는 3 * 3 제품 4 개 와 6 * 6 제품 이 있 는데 이때 4 개 3 * 3 제품 은 한 상 자 를 차지 하고 다른 6 * 6 제품 은 1 개의 상 자 를 차지 하기 때문에 상자 수 는 2 입 니 다.2 조 는 1 * 1 제품 7 개, 2 * 2 제품 5 개, 3 * 3 제품 1 개가 있 는데 우 리 는 그들 을 모두 한 상자 에 넣 을 수 있 기 때문에 수출 은 1 이 라 고 밝 혔 다.6 개 모델 의 제품 이 상 자 를 차지 하 는 구체 적 인 상황 을 분석 하면 다음 과 같다. 6 * 6 의 제품 은 각각 하나의 완전한 상 자 를 차지 하고 공간 이 없다.5 * 5 의 제품 은 각각 새로운 상 자 를 차지 하고 1 * 1 을 담 을 수 있 는 11 개의 공간 을 남 깁 니 다.4 * 4 의 제품 은 각각 새로운 상 자 를 차지 하고 2 * 2 를 담 을 수 있 는 5 개의 공간 을 남 깁 니 다.3 * 3 의 제품 은 상황 이 비교적 복잡 합 니 다. 먼저 3 * 3 의 제품 은 원래 5 * 5 또는 4 * 4 가 담 긴 상자 에 넣 을 수 없습니다. 그러면 3 * 3 의 제품 을 위해 새로운 상 자 를 따로 열 어야 합 니 다. 새로 연 상자 의 수량 은 3 * 3 의 제품 의 수량 을 4 로 나 누 어 정리 해 야 합 니 다.아울러 3 * 3 의 제품 을 위해 상 자 를 새로 열 때 남 은 공간 에 2 * 2 와 1 * 1 의 제품 을 얼마나 담 을 수 있 는 지 (여기에 2 * 2 의 제품 을 담 을 수 있 는 공간 이 있 으 면 2 * 2 의 여유 공간 에 계산 해 2 * 2 의 제품 이 모두 담 길 때 까지 기 다 렸 다가 2 * 2 의 빈 공간 이 남 으 면 1 * 1 의 여유 공간 으로 전환) 에 대해 논의 할 필요 가 있다.우 리 는 상황 에 따라 3 * 3 의 제품 으로 열 린 새 상자 에 남 은 빈 자 리 를 토론 할 수 있 습 니 다. 모두 네 가지 상황 입 니 다. 첫 번 째, 3 * 3 의 제품 의 수량 은 바로 4 의 배수 이기 때문에 공간 이 없습니다.두 번 째, 3 * 3 의 제품 수 는 4 의 배수 에 1 을 더 한 것 으로 이때 2 * 2 의 빈자리 5 개 와 1 * 1 의 빈자리 7 개가 남 았 다.세 번 째, 3 * 3 의 제품 수 는 4 의 배수 에 2 를 더 한 것 으로 이때 2 * 2 의 빈자리 3 개 와 1 * 1 의 빈자리 6 개가 남 았 다.네 번 째, 3 * 3 의 제품 수 는 4 의 배수 에 3 을 더 한 것 으로 이때 2 * 2 의 빈자리 1 개 와 1 * 1 의 빈자리 5 개가 남 았 다.3 * 3 제품 을 다 처리 하면 남 은 2 * 2 의 빈자리 와 2 * 2 제품 의 수 를 비교 해 볼 수 있 고, 제품 수가 많 으 면 2 * 2 의 빈 자 리 를 모두 채 우 고 2 * 2 의 제품 을 위해 새 상 자 를 열 어 주 는 동시에 새 상자 중 1 * 1 의 빈 자 리 를 계산 해 빈자리 가 많 으 면 2 * 2 제품 을 모두 2 * 2 의 빈 자 리 를 채 우 고,나머지 2 * 2 의 빈 자 리 를 1 * 1 의 빈 자리 로 변환 합 니 다.마지막 으로 1 * 1 의 제품 을 처리 하고 1 * 1 의 빈자리 와 1 * 1 의 제품 수 를 비교 해 보 세 요. 빈자리 가 많 으 면 1 * 1 의 제품 을 모두 빈자리 에 채 우 고 그렇지 않 으 면 1 * 1 의 빈 자 리 를 채 운 다음 1 * 1 의 제품 을 위해 새로운 상 자 를 엽 니 다.
코드

Source Code

Problem: 1017       User: liangrx06
Memory: 132K        Time: 16MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

bool input(int a[])
{
    bool flag = false;
    for (int i = 1; i <= 6; i ++) {
        scanf("%d", &a[i]);
        if (a[i] != 0) flag = true;
    }
    return flag;
}

int main(void)
{
    int a[7];
    int i, k, m, res;

    while (input(a)) {
        res = 0;
        for (i = 6; i >= 1; i --) {
            k = (6/i)*(6/i);//        i      
            m = a[i]/k;//       
            a[i] %= k;
            int n1 = 6*6*m - i*i*m*k;//     1*1
            if (a[i]) n1 += 6*6 - i*i*a[i];
            if (i == 3 || i == 4) {
                int n2 = 0;//     2*2
                if (i == 4)
                    n2 += 5*m;
                else if (i == 3 && a[i])
                    n2 += (4-a[i])*2 - 1;
                if (n2 > a[2])
                    n2 = a[2];
                a[2] -= n2;
                //printf("n1=%d, n2=%d
", n1, n2);
                n1 -= 2*2*n2;
                //printf("n1=%d, n2=%d
", n1, n2);
            }
            if ( i >= 2 && i <= 5 ) {
                if (n1 > a[1])
                    n1 = a[1];
                a[1] -= n1;
            }
            //for (int x = 1; x <= 6; x ++)
            //  printf("%d ", a[x]);
            //printf("
");
            res += m;
            if (a[i])
                res ++;
            a[i] = 0;
        }
        printf("%d
", res);
    }

    return 0;
}

POJ3040
Allowance
제목
N 가지 서로 다른 액면 의 지폐 가 있 습 니 다. 당신 이 고용 한 사람 은 매번 적어도 C 원 을 지불 합 니 다.각 지폐의 액면 크기 는 V (각 지폐의 크기 는 전체 배수 관계 가 되 는 것 이 문제 해결 의 관건) 이 고, 장 수 는 B 인 데, 최대 몇 번 까지 지불 할 수 있 느 냐 고 물 었 다.
사고의 방향
V 를 작은 것 부터 큰 것 까지 배열 합 니 다.
1. 먼저 C 원 이상 의 지 폐 를 사용 하고 계산 을 한다.
2. 큰 지 폐 를 잡 으 면 많이 잡 을 수록 좋 지만 C 보다 작 아야 한다. C 와 같 으 면 하나의 계 수 를 하고 C 보다 작 으 면 작은 지 폐 를 어 릴 때 부터 잡 으 면 C 보다 크 면 하나의 계 수 를 한다.지 폐 는 배수 관계 이기 때문에 당신 의 가장 큰 지폐의 액면가 가 앞의 모든 지폐의 액면가 보다 큽 니 다.
3. 마지막 으로 지불 상황 의 총 가 를 진행 하 는 것 은 다음 에 이 두 번 째 단계 처럼 지불 방안 의 개 수 를 계산 한 다음 에 두 번 째 단계 부터 지불 할 수 없 을 때 까지 계속 할 수 있다 는 뜻 이다.
코드

Source Code

Problem: 3040       User: liangrx06
Memory: 212K        Time: 16MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20;

struct Coin {
    int v, b;
};

bool cmp(const Coin &x, const Coin &y)
{
    return x.v < y.v;
}

int n, c;
int m[N];
Coin coin[N];

int sum;
bool choose(int i)
{
    m[i] = sum / coin[i].v;
    if (m[i] > coin[i].b)
        m[i] = coin[i].b;
    sum -= m[i]*coin[i].v;
    if (sum == 0)
        return true;
    if (i == 0 || choose(i-1) == false) {
        if (coin[i].b > m[i]) {
            sum -= coin[i].v;
            m[i] ++;
            return (sum <= 0);
        }
        return false;
    }
    return true;
}

bool canPay()
{
    memset(m, 0, sizeof(m));
    sum = c;
    return choose(n-1);
}

int main(void)
{
    int i;

    cin >> n >> c;
    for (i = 0; i < n; i ++)
        cin >> coin[i].v >> coin[i].b;
    sort(coin, coin+n, cmp);

    int res = 0;
    while (canPay()) {
        int k = (int)1e9;
        //for (i = 0; i < n; i ++)
        // printf("%d ", m[i]);
        //printf("
");
        for (i = 0; i < n; i ++) {
            if (m[i] > 0) {
                int t = coin[i].b / m[i];
                k = (t < k) ? t : k;
            }
        }
        for (i = 0; i < n; i ++) {
            if (m[i] > 0) {
                coin[i].b -= m[i] * k;
            }
        }
        res += k;
        //break;
    }
    printf("%d
", res);

    return 0;
}

POJ1862
Stripies
제목
과학자 들 은 무게 weight 가 있 는 이상 한 물건 을 발견 했다. 만약 그들 이 부 딪 히 면 총 무 게 는 2 * sqrt (m1 * m2) 가 된다.최종 중량 의 최소 치 를 요구 하 다.
사고의 방향
시험 해 보면 무게 가 비교적 큰 것 을 먼저 건 드 리 면 여러 번 sqrt 를 건 드 려 마지막 결 과 를 최소 화 할 수 있다.
코드

Source Code

Problem: 1862       User: liangrx06
Memory: 220K        Time: 16MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 10000;

int n;
double a[N];

void input()
{
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
    }
}

double coll(double x, double y)
{
    return 2*sqrt(x*y);
}

double solve()
{
    sort(a, a+n);
    for (int i = n-2; i >= 0; i --)
        a[i] = coll(a[i], a[i+1]);
    return a[0];
}

int main(void)
{
    input();

    double res = solve();
    printf("%.3lf
", res);

    return 0;
}

POJ3262
Protecting the Flowers
제목
n 마리 의 소 가 FJ 의 화원 에서 마구 먹는다.그래서 FJ 는 그들 을 외양간 으로 돌려 보 내야 한다.모든 소 는 쫓 겨 나 기 전에 매 초 에 디 개의 꽃 을 먹는다.쫓 아내 고 FJ 왔 다 갔다 하 는 데 걸 리 는 시간 은 Ti 입 니 다.×2。쫓 겨 나 는 과정 에서 쫓 겨 난 소 는 함부로 먹 을 수 없다.
사고의 방향
욕심 전략, 소 를 정렬 하 는 기준 은 소 A 와 소 B 가 한 마 리 를 골 라 내 려 고 한다 고 가정 하면 우 리 는 먼저 가장 큰 소 한 마 리 를 파괴 하고 작은 소 를 파괴 하 는 것 을 선택해 야 한다.그들의 파 괴 는 어떻게 계산 합 니까?소 A 를 먼저 쫓 아 낸다 고 가정 하면 소 B 가 입 힌 손실 은 2 이다.×TA×DB, 소 B 부터 쫓 아내 면 소 A 로 인 한 피 해 는 2 입 니 다.×TA×DB, 그 러 니까 TA 만 판단 하면×DB 와 TA×DB 가 큰 사람 은 누 구 를 먼저 내 쫓 아야 할 지 알 기 때문에 배열 정렬 의 기준 은 - Ti 이다.×Dj>Tj×Di。
코드

Source Code

Problem: 3262       User: liangrx06
Memory: 1780K       Time: 141MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100000;

struct Cow {
    int t, d;
    double v;
};

int n;
Cow cow[N];

void input()
{
    cin >> n;
    for (int i = 0; i < n; i ++) {
        scanf("%d%d", &cow[i].t, &cow[i].d);
        cow[i].v = (double)(cow[i].d)/(double)(cow[i].t);
    }
}

bool cmp(const Cow &x, const Cow &y)
{
    return x.v > y.v;
}

void solve()
{
    sort(cow, cow+n, cmp);

    long long res = 0;
    int time = 0;
    res += time * cow[0].d;
    for (int i = 1; i < n; i ++) {
        time += 2*cow[i-1].t;
        res += time * cow[i].d;
    }
    printf("%lld
", res);
}

int main(void)
{
    input();

    solve();

    return 0;
}