글 읽기 - 그리디 예외를 모르겠습니다.

lim551 5년 전 0

제가 사용한 방법은 (e-s)가 작은 구간을 우선적으로 채워가는 식으로 구현했는데, USACO 입력을 넣어보니 최적해보다 작게 나오는 경우가 있었습니다.

어떤 예외가 있을까요?

또 USACO 해설에서 a < b < c < d 일 때, [a, d] 구간보다 [b, c] 구간을 선택하는게 무조건 이득이라는 아이디어를 이용해서 아래와 같이 구현을 했던데,

저러면 a < b < c < d 일 때 [a, c], [b, d] 구간과 같이 서로 걸쳐있을 때 처리가 무조건 c, d중 큰 것을 무시해가면서 반복을 하는데,

왜 두 구간 중 끝 점이 큰 것을 지워도 되는지 이해가 안 갑니다.

// 제 코드
/************
< 주소 >      : 
*************
< 해결방안 >   :


*************
< 오답노트 >   :

*************/

#ifndef ONLINE_JUDGE
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <bits/stdc++.h>
using namespace std;

// ........................macro.......................... //
// [i, n)
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
// [i, n]
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
typedef pair<int, int> ii;
typedef pair<int, pair<int, int> > iii;
typedef long long i64;
typedef unsigned long long ui64;
inline i64 GCD(i64 a, i64 b) { while(b != 0) { int t = a; a = b; b = t % b; } return a; }
inline i64 LCM(i64 a, i64 b) { if (a == 0 || b == 0) return GCD(a, b); return a*b / GCD(a, b); }
inline i64 CEIL(i64 n, i64 d) { return n / d + n % d != 0; }
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d)*2 >= d); }
inline i64 POW(i64 a, i64 n) {
	if (n < 0) return 0;
	i64 ret = 1;
	while (n) { if (n % 2) ret *= a; a = a * a; n /= 2; }
	return ret;
}

// ....................................................... //

struct node { int s, e, m; int d() { return e - s; }};
struct segtree {
	int n, h;
	vi t, d;
	void init(int _n) {
		n = _n;
		t = vi(2*n, 0), d = vi(n, 0);
		h = sizeof(n)*8 - __builtin_clz(n);
	}
	void apply(int u, int x) {
		if(u < n) d[u] += x;
		t[u] += x; // 여기서도 t[u]를 갱신해줘야 함.
	}
	void build(int u) {
		while (u > 1) u /= 2, t[u] = max(t[u*2], t[u*2+1]) + d[u];
	}
	void push(int p) {
		for (int s = h; s > 0; --s) {
			int i = p >> s;
			if (d[i] != 0) {
				apply(i*2, d[i]);
				apply(i*2+1, d[i]);
				d[i] = 0;
			}
		}
	}
	void inc(int s, int e, int x) {
		s += n, e += n;
		int s0 = s, e0 = e;
		for (; s < e; s /= 2, e /= 2) {
			if (s%2) apply(s++, x);
			if (e%2) apply(--e, x);
		  }
		build(s0);
		build(e0-1);
	}
	int query(int s, int e) {
		s += n, e += n;
		push(s);
		push(e - 1);
		int ret = -2e9;
		for (; s < e; s /= 2, e /= 2) {
			if (s%2) ret = max(ret, t[s++]);
			if (e%2) ret = max(t[--e], ret);
		}
		return ret;
	}
};
const int MAXK = 5e4;
int k, n, c;
node ar[MAXK];
void input() {
	cin >> k >> n >> c;
	FOR(i, 0, k) cin >> ar[i].s >> ar[i].e >> ar[i].m;
}

segtree st;
int solve() {
	st.init(n+1);
	sort(ar, ar + k, [](node& u, node& v) { if(u.d() == v.d()) return u.m > v.m; return u.d() < v.d(); });
	int ans = 0;
	FOR(i, 0, k) {
		int f = min(ar[i].m, c - st.query(ar[i].s, ar[i].e));
		ans += f;
		st.inc(ar[i].s, ar[i].e, f);
	}
	cout << ans << ENDL;
}

// ................. main .................. //
void execute() {
	input(), solve();
}

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	cin.tie(0); ios_base::sync_with_stdio(false);
	execute();
}
// ......................................... //

// USACO 해답
#include <fstream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

struct group
{
    int M;
    int S;
    int E;

    bool operator<(const group &b) const
    {
        return S < b.S;
    }
};

int main()
{
    ifstream in("shuttle.in");
    ofstream out("shuttle.out");
    int K, N, C;
    int ans = 0;

    in >> K >> N >> C;
    vector groups(K);
    for (int i = 0; i < K; i++)
        in >> groups[i].S >> groups[i].E >> groups[i].M;

    sort(groups.begin(), groups.end());

    map<int, int> off;      // number getting off at time t
    int total = 0;          // number on shuttle
    for (int i = 0; i < K; i++)
    {
        int pos = groups[i].S;
        map<int, int>::iterator p = off.begin();
        while (p != off.end() && p->first <= pos)
        {
            ans += p->second;
            total -= p->second;
            off.erase(p++);
        }

        off[groups[i].E] += groups[i].M;
        total += groups[i].M;
        p = off.end();
        --p;
        while (total > C)
        {
            if (total - p->second >= C)
            {
                total -= p->second;
                off.erase(p--);
            }
            else
            {
                p->second -= total - C;
                total = C;
            }
        }
    }
    ans += total;
    out << ans << "\n";
    return 0;
}

jh05013 5년 전 1

길이 우선일 때 반례입니다.

lim551 5년 전 0

아... 감사합니다!

뭐가 문젠지 몰라 답답했었는데 덕분에 꿀잠 잘 수 있을거 같습니다 ㅋㅋ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그리디 예외를 모르겠습니다.

lim551 5년 전 0

jh05013 5년 전 1

lim551 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말