科技网站设计,内江市住房和城乡建设局网站,中原区快速建站公司电话,自己做的网站买域名多少钱【题目分析】
觉得是一道挺考验贪心掌握程度的题目#xff0c;我就算知道是要用贪心而且肯定和区间有关#xff0c;肯定要进行一下排序什么的我还是没有找到合适的贪心策略。
经过大佬的博客后我才明白如何进行贪心。
如果没有任何提示看这道题#xff0c;首先#xff0…【题目分析】
觉得是一道挺考验贪心掌握程度的题目我就算知道是要用贪心而且肯定和区间有关肯定要进行一下排序什么的我还是没有找到合适的贪心策略。
经过大佬的博客后我才明白如何进行贪心。
如果没有任何提示看这道题首先我们要有将复杂问题分解的能力即这里要发现两个维度之间是没有什么关系的所以可以分开进行然后在一起输出结果。
其次我们要找到合适的贪心策略。正如大佬所说贪心是问题导向的我们不能盲目的排一下序然后试试要观察问题想要的是什么。在这里我们想要的是每个行列也是相同的这里就都当作行进行讨论都有一个车。我们考虑从前往后放车放哪个车比较合适呢有很多车子的可行区间都包含这个点我们要在这些车里面选择哪一个直观上我们选取右区间最小的包含这个点的车最好当然是没有被选过的。想到这个策略需要一些灵感而这个策略的正确性也是可以直观上感受的从前往后我们每个格子选择的车都是右区间最小的那么这就给后面的车留下了更多的可能性总是最优的。
这里的车是一种必要的竞争关系尽可能的减少对手就能够使后面的选择更加游刃有余如果很多可以选择后面的车选择了前面那么后面的行就面临没有车可以选的危险。
emmm,正确性应该也是可以证明的但是想到这种贪心策略分析正确性的时候我们不会进行严格的数学证明还是太笨这样太慢太浪费时间更多的是依靠直(xuan)觉(xue)。
【AC代码】
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN5e35;
int n;
struct node
{int l,r,idx;
}a1[MAXN],a2[MAXN];int vis[MAXN];int b1[MAXN],b2[MAXN];bool cmp(node a,node b)
{return a.rb.r;
}int main()
{while(~scanf(%d,n) n){for(int i1;in;i){scanf(%d%d%d%d,a1[i].l,a2[i].l,a1[i].r,a2[i].r);a1[i].idxa2[i].idxi;}sort(a11,a11n,cmp);memset(vis,0,sizeof(vis));bool flag;for(int i1;in;i){flagfalse;for(int j1;jn;j){if(!vis[j] a1[j].li a1[j].ri){vis[j]true; b1[a1[j].idx]i;flagtrue;break;}}if(!flag) break;}if(!flag){printf(IMPOSSIBLE\n);continue;}sort(a21,a21n,cmp);memset(vis,0,sizeof(vis));for(int i1;in;i){flagfalse;for(int j1;jn;j){if(!vis[j] a2[j].li a2[j].ri){vis[j]true; b2[a2[j].idx]i;flagtrue;break;}}if(!flag) break;}if(!flag){printf(IMPOSSIBLE\n);continue;}for(int i1;in;i){printf(%d %d\n,b1[i],b2[i]);}}return 0;
}
