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); else dp[a[i].mo]=min(dp[a[i].mo],a[i].time); } if(ans!=INF) printf("%d\n",ans); else printf("oh no!\n"); } int main() { while(~scanf("%d %d",&n,&m)) { init(); } return 0; }
找 列最小 水过的, 隔壁 找行最小 水过的, 然后 重判后 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; else r=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
