Rezolvare completă PbInfo #2431 cover

Se consideră N intervale închise, având extremităţile numere naturale cuprinse între 1 şi L. Fiecare număr natural i din intervalul [1, L] are asociată o pondere c[i]. Numim acoperire o mulţime de numere naturale cuprinse între 1 şi L cu proprietatea că fiecare interval conţine cel puţin un element al mulţimii. Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.

Cerința

Pentru un set de intervale dat să se determine costul minim al unei acoperiri.

Date de intrare

Fișierul de intrare cover.in conţine pe prima linie cele două numere naturale N L separate printr-un spaţiu. Pe următoarea linie se află L numere naturale separate prin câte un spaţiu c[1] c[2] ... c[L] reprezentând ponderile numerelor naturale din intervalul [1, L]. Următoarele N linii conţin fiecare câte două numere naturale a b (1 ≤ a ≤ b ≤ L) reprezentând extremităţile intervalelor.

Date de ieșire

Fișierul de ieșire cover.out va conţine o singură linie pe care va fi scris un număr natural reprezentând costul minim al unei acoperiri.

Restricții și precizări

  • 1 ≤ N ≤ 60 000
  • 1 ≤ L ≤ 1 000 000
  • 0 ≤ c[i] ≤ 1024, pentru orice 1 ≤ i ≤ L
  • Pentru 40% din teste N ≤ 1000 şi L ≤ 10000.

Exemplul 1:

cover.in

2 5
100 5 9 6 90
1 3
3 5

cover.out

9

Explicație

Se construieşte acoperirea {3} care are costul 9. Elementul 3 aparţine ambelor intervale date în fişierul de intrare.
Există şi alte acoperiri posibile de exemplu {2, 4} dar costul acesteia este 11 care nu este minim.

Exemplul 2:

cover.in

4 10
1 3 6 4 5 1 0 1 3 2
1 3
3 5
6 9
4 4

cover.out

5

Explicație

Se construieşte acoperirea {1, 4, 7} care are costul 5.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema cover:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define FOR(i, a, b) for (i = (a); i <= (b); i ++)
#define REP(i, n)    for (i =   0; i <  (n); i ++)
#define PB           push_back
#define MP           make_pair
#define PII          pair<int, int>

#define INF  1999999999
#define NMAX 1000005

int w[NMAX], m[NMAX];
vector<PII> E, F;
int N, K, R, i, j, k, q, Ans = INF;

int v[NMAX], t[NMAX], vb, ve;

inline void push(int key, int time)
{
    for (; vb <= ve && key < v[ve]; ve--);
    ++ve, v[ve] = key, t[ve] = time;
}

inline void pop(int time)
{
    for (; vb <= ve && t[vb] < time; vb++);
}

int cmp(PII a, PII b)
{
    if (a == b) return a.first > b.first ? 1 : 0;
    else return a.second < b.second ? 1 : 0;
}

int main(void)
{
    freopen("cover.in", "r", stdin);
    freopen("cover.out", "w", stdout);

    scanf("%d %d", &R, &N);
    FOR(i, 1, N) scanf("%d", &w[i]);

    REP(k, R) scanf("%d %d", &i, &j), F.PB(MP(i, j));
    sort(F.begin(), F.end(), cmp);
    int lst = 0;
    FOR(i, 0, R-1)
        if (F[i].first > lst)
            E.PB(F[i]), lst = F[i].first;
//  fprintf(stderr, "|E| = %d\n", E.size());

    m[0] = 0;
    vb = ve = 0, v[0] = t[0] = 0;

    q = -1;
    FOR(i, 1, N)
    {
        // bag intervale inchise
        for (; q + 1 < E.size() && E[q+1].second < i; q++);
        if (q >= 0) pop(E[q].first);
        m[i] = w[i]+v[vb];
        push(m[i], i);
    }

    FOR(i, E[E.size()-1].first, E[E.size()-1].second)
        if (m[i] < Ans)
            Ans = m[i];
    
    printf("%d\n", Ans);
//  fprintf(stderr, "Ans = %d\n", Ans);

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2431 cover

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2431 cover de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!