本文主要是介绍2017 ICPCECIC 北方邀请赛 H MJF wants to work (贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
MJF wants to work
时间限制: 1 Sec 内存限制: 128 MB提交: 87 解决: 16
[ 提交][ 状态][ 讨论版]
题目描述
MJF feel the summer vacation is very leisure. So he wants to work to earn money.
There are n jobs MJF can take part in.For job i, it has the start time ti.x, the end time ti.y and reward ci.
MJF wants to take part in two jobs (exact two jobs), and he wants to earn exactly M yuan. He doesn't want to earn one money more,he thinks it's a waste.
Becase MJF is a lazy boy, so he wants the time of the sum of two jobs shortest.
Becase MJF can only take part in one job in a time.So two jobs can't overlap.(ti.y < tj.x)
There are n jobs MJF can take part in.For job i, it has the start time ti.x, the end time ti.y and reward ci.
MJF wants to take part in two jobs (exact two jobs), and he wants to earn exactly M yuan. He doesn't want to earn one money more,he thinks it's a waste.
Becase MJF is a lazy boy, so he wants the time of the sum of two jobs shortest.
Becase MJF can only take part in one job in a time.So two jobs can't overlap.(ti.y < tj.x)
输入
The input consists of multiple test cases.
For each test，the first line contains 2 integers n, m.(1 <= n, m <= 2e5)
Then following n lines, each line contains 3 integers ti.x, ti.y, ci.(1 <= ti.x, ti.y, ci <= 2e5)
For each test，the first line contains 2 integers n, m.(1 <= n, m <= 2e5)
Then following n lines, each line contains 3 integers ti.x, ti.y, ci.(1 <= ti.x, ti.y, ci <= 2e5)
输出
For each test case, print the value of the sum of two jobs' time.if there are no answer,please print"oh no!"
样例输入
3 10
1 2 3
3 4 7
4 6 7
1 10
1 10 10
样例输出
4
oh no!
123
思路为:
把 时间段 从线段 化成 左右两个端点 问题, 每个端点存 时间, 金钱 和 区分左右标志,
然后按照 左端点从小到大排序, 并且是 一左一右 排序, 遇到左端点, 维护ans 值, dp数组存的是 时间, 维护 m- 当前已挣得钱的 时间 尽可能小
遇到右端点 维护 dp 时间
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#define mem(a,b) memset(a,b,sizeof(a))
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
#define S1(n) scanf("%d",&n)
#define SL1(n) scanf("%I64d",&n)
#define S2(n,m) scanf("%d%d",&n,&m)
#define SL2(n,m) scanf("%I64d%I64d",&n,&m)
#define Pr(n) printf("%d\n",n)
using namespace std;
typedef long long ll;
const double PI=acos(-1);
const int INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e6+5;
const int MOD=1e9+7;
const int mod=1e9+7;
int dir[5][2]={0,1,0,-1,1,0,-1,0};int n,m;
int cont;
int dp[maxn*2];// dp数组存的是时间
struct node{int x;int time;int mo;int flag;//0 左端点, 1 右端点
}a[maxn*2];
int cmp(node a,node b)
{if(a.x==b.x)return a.flag<b.flag;return a.x<b.x;}
void init()
{for(int i=0;i<=maxn;i++)dp[i]=INF;int x,y,z;mem(a,0);cont=0;for(int i=1;i<=n;i++){scanf("%d %d %d",&x,&y,&z);a[++cont].x=x;a[cont].time=y-x+1;a[cont].flag=0;a[cont].mo=z;a[++cont].x=y;a[cont].time=y-x+1;a[cont].flag=1;a[cont].mo=z;}sort(a+1,a+cont+1,cmp);int ans=INF;for(int i=1;i<=cont;i++){if(a[i].flag==0)ans=min(ans,dp[m-a[i].mo]+a[i].time);elsedp[a[i].mo]=min(dp[a[i].mo],a[i].time);}if(ans!=INF)printf("%d\n",ans);elseprintf("oh no!\n");}
int main()
{while(~scanf("%d %d",&n,&m)){init();}return 0;
}
Coach's plan
时间限制: 2 Sec 内存限制: 128 MB提交: 57 解决: 15
[ 提交][ 状态][ 讨论版]
题目描述
NEUACM team holds summer training every year. This year n students participate in the training, and we provide m computers. Everyone has a suitability (0<=suitability<=1000) to every computer.
Now our coach needs to draw up a plan, which satisfies:
1. every student uses one computer, and a computer can be used by no more than one student;
2. maximize the minimum suitability, which means if the answer is w, then everyone's suitability to his computer shouldn't be less than w.
Hint: huge input, please use fast IO.
Now our coach needs to draw up a plan, which satisfies:
1. every student uses one computer, and a computer can be used by no more than one student;
2. maximize the minimum suitability, which means if the answer is w, then everyone's suitability to his computer shouldn't be less than w.
Hint: huge input, please use fast IO.
输入
The first line contains n and m (1<=n<=m<=500), indicating the number of students and computers.
Next n lines describes every student's suitability to every computer, number in ith line and jth row means student[i]'s suitability to computer[j].
Next n lines describes every student's suitability to every computer, number in ith line and jth row means student[i]'s suitability to computer[j].
输出
A single number w in one line, which is described before.
样例输入
1 2
1 10
2 3
10 1 2
2 1 1
样例输出
10
2
找 列最小 水过的, 隔壁 找行最小 水过的, 然后 重判后 game over 隔隔壁, 找行列 最小 依然坚挺 ; mmp
水过代码: 找 行小列小, min 最小的,
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int n,m,a[505][505],b[505],c[505];bool cmp(int x, int y){return x > y;
}int main(){while(~scanf("%d%d",&n,&m)){for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++)scanf("%d",&a[i][j]);}for(int i = 0; i < n; i ++){int mxx = a[i][0];for(int j = 1; j < m; j ++)mxx = max(a[i][j],mxx);b[i] = mxx;}for(int j = 0; j < m; j ++){int mxx = a[0][j];for(int i = 1; i < n; i ++)mxx = max(a[i][j],mxx);c[j] = mxx;}sort(b,b+n,cmp);sort(c,c+m,cmp);printf("%d\n",min(c[n-1],b[n-1]));}return 0;
}正解是: 二分图匹配 + 二分查找;
把网格 从 一维 变成 二维 匹配 问题, 用到匈牙利算法,
比赛时, 考虑到 二分图匹配, 没 想到 要用到二分查找,
要用 链式前向星 存储 边l
1w 小心 , 一不小心 就超时;
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#define mem(a,b) memset(a,b,sizeof(a))
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
#define S1(n) scanf("%d",&n)
#define SL1(n) scanf("%I64d",&n)
#define S2(n,m) scanf("%d%d",&n,&m)
#define SL2(n,m) scanf("%I64d%I64d",&n,&m)
#define Pr(n) printf("%d\n",n)
using namespace std;
typedef long long ll;
const double PI=acos(-1);
const int INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e6+5;
const int MOD=1e9+7;
const int mod=1e9+7;
int dir[5][2]={0,1,0,-1,1,0,-1,0};int n,m;
int maps[505][505];
struct Edge{int v,u;
}a[maxn];
int edge_cont;
int head[10005];
int match[10005];
bool used[10005];
void add(int u,int v)
{a[++edge_cont].v=v;a[edge_cont].u=head[u];head[u]=edge_cont;
}
int finds(int x)
{used[x]=1;for(int i=head[x];i!=-1;i=a[i].u)// 链式前向星 访问{int v=a[i].v;int w=match[v];if(w<0||!used[w]&&finds(w))// v 还没匹配 或者 能够找到更合适的{match[x]=v;match[v]=x;return 1;}}return 0;
}
int binary_match()//二分匹配
{int ans=0;mem(match,-1);for(int i=0;i<n;i++){if(match[i]<0)//未匹配{mem(used,0);if(finds(i))//可以找到合适的ans++;}}return ans;
}
bool judge(int x)
{edge_cont=0;mem(head,-1);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(maps[i][j]>=x){add(i,j+n); //无向图add(j+n,i);}}}if(binary_match()==n)return true;return false;
}
void work()
{int ans;int l=0;int r=1001;while(r-l>1){int mid=(l+r)>>1;if(judge(mid))l=mid;elser=mid;}cout<<l<<endl;
}
int main()
{while(~scanf("%d %d",&n,&m)){mem(maps,0);mem(a,0);min_num=INF;max_num=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++){scanf("%d",&maps[i][j]);}work();}return 0;
}
123
这篇关于2017 ICPCECIC 北方邀请赛 H MJF wants to work (贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
