P1986 元旦晚会

一道可以用各种各样的办法做的（水）题

在这里就介绍两种做法

题意：

自己看看吧，很明显的意思，就是求前i个人最少有多少个话筒。

解法1：差分约束

设\(dis[i]\)表示前\(i\)个人最少有多少个话筒

根据题目意思每个人都只能有一个话筒所以 \(dis[i[+1>=dis[i+1] dis[i+1]>=dis[i]\)

\(a_i\)到\(b_i\)至少有\(c_i\)个所以 \(dis[a_i-1]+c_i>=dis[b_i]\)

转换一下跑一遍最长路即可。

CODE:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<cmath>

#define N 30010

#define M 5050

#define INF 214748364

using namespace std;

struct edge {

    int to;

    int from;

    int data;

}e[N * 2 + 1];

int head[N],cnt;

int dis[N],m,n;

bool vis[N];

queue<int > q;

inline void add_edge(int x,int y,int z) {

    e[++cnt].from = y;

    e[cnt].data = z;

    e[cnt].to = head[x];

    head[x] = cnt;

}

void spfa() {

    for(int i = 1 ; i <= n ; i++)

    	dis[i] = -19260817;

    dis[1] = 0;

    q.push(1);

    vis[1] = true;

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = head[u] ; i ; i = e[i].to) {

            int v = e[i].from;

            if(dis[u] + e[i].data > dis[v]) {

                dis[v] = dis[u] + e[i].data;

                if(!vis[v]) {

                    q.push(v);

                    vis[v] = true;

                }

            }

        }

    }

}

int main() {

    //n = read(), m = read();

    scanf("%d%d",&n,&m);

    while(m--) {

        //int l = read(), r = read(), k = read();

        int u , v , w;

        scanf("%d%d%d",&u,&v,&w);

        add_edge(u - 1 , v , w);

    }

    for(int i = 1 ; i <= n ; i++) {

        add_edge(i - 1 , i , 0);

        add_edge(i , i - 1 , -1);

    }

    spfa();

    printf("%d\n", dis[n]);

    return 0;

}

啥，你不想写SPFA。不过没关系，我们还有另一种做法。

解法2：贪心

我们可以先按所有声部的右端点排序，再进行从后到前的顺序选取拿话筒的人。很显然，如果我们从后往前选取，就会尽量满足后面人的需求，这样就能达到最小值。

CODE:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N = 31000;

struct node {

    int a;

    int b;

    int c;

}e[N];

int m,n,ans;

int vis[N];

inline bool cmp(node x,node y) {

    if(x.b != y.b)

        return x.b < y.b;

    return x.a < y.a;

}

void init() {

    scanf("%d%d",&n,&m);

    for(int i = 1 ; i <= m ; i++)

        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);

}

void work() {

    sort(e+1 , e + m + 1 , cmp);

    for(int i = 1 ; i <= m ; i++) {

        int cnt = 0;

        for(int j = e[i].b ; j >= e[i].a ; j--) {

            if(vis[j]) cnt++;

        }

        if(cnt > e[i].c) continue;

        else {

            for(int j = e[i].b ; (j >= e[i].b - e[i].c + 1 && cnt < e[i].c) ; j--) {

                if(!vis[j]) vis[j] = 1 , cnt++ , ans++;

            }

        }

    }

    printf("%d\n",ans);

}

int main() {

    init();

    work();

    return 0;

}

巴特西

P1986 元旦晚会

一道可以用各种各样的办法做的（水）题

题意：

解法1：差分约束

CODE:

啥，你不想写SPFA。不过没关系，我们还有另一种做法。

解法2：贪心

CODE:

最新文章

热门文章