51nod1205(johnson)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1205

题意：中文题诶～

思路：johnson模板题

流水作业调度问题的Johnson算法：

(1)令N1={i|ai<bi}, N2={i|ai>=bi}；

(2)将N1中作业按ai的非减序排序；将N2中作业按bi的非增序排序；

(3)N1中作业接N2中作业构成满足Johnson法则的最优调度。

关于johnson算法详细讲解：http://blog.csdn.net/liufeng_king/article/details/8678316

代码：

 #include <iostream>

 #include <stdio.h>

 #include <algorithm>

 using namespace std;

 const int MAXN = 5e4+;

 struct node{

     int x, y, cnt;

 }gg[MAXN];

 bool cmp(node a, node b){

     return a.cnt < b.cnt;

 }

 bool cmp1(node a, node b){

     return a.x < b.x;

 }

 bool cmp2(node a, node b){

     return a.y > b.y;

 }

 int main(void){

     int n;

     scanf("%d", &n);

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

         scanf("%d%d", &gg[i].x, &gg[i].y);

         gg[i].cnt = gg[i].x-gg[i].y;

     }

     sort(gg, gg+n, cmp);

     int index = ;

     while(gg[index].cnt < ){

         index++;

     }

     sort(gg, gg+index, cmp1);

     sort(gg+index, gg+n, cmp2);

     int ans = gg[].x + gg[].y;

     int sum = gg[].x;

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

         sum += gg[i].x;

         ans = max(sum, ans) + gg[i].y;

     }

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

     return ;

 }

巴特西

51nod1205(johnson)

最新文章

热门文章