洛谷 1761 正方形-白红宇的个人博客

洛谷 1761 正方形

发布日期：2022-02-05 18:27:29 浏览次数：17 分类：技术文章

本文共 1253 字，大约阅读时间需要 4 分钟。

题目描述

有n个大小不一的正方形，现将它们依次以45度斜放入第一象限，每个正方形都要与x轴有一个交点，且不能与之前放入的正方形重叠。在此前提下，正方形与x轴交点的坐标应尽可能小。问这样放置后，从上往下看，至少能部分被看见的正方形有哪些？

输入格式

每个测试点包含多组测试数据。每个测试数据的第一行是一个整数n，第二行是n个正整数，表示每个正方形的变长。输入以一行单独的0结束。

输出格式

对于每个测试数据输出一行，增序输出至少可看到部分的正方形的编号，用空格隔开。

样例输入

4

3 5 1 4

3

2 1 2

0

样例输出

1 2 4

1 3

注释

对于50%的数据，n<=10 ；

对于100%的数据，n<=50 正方形的大小不超过30。

大模拟题

一开始感觉太麻烦了放一个不仅由前一个影响还可能由前面的好几个限制

而且实数还有误差。。。。

导致模拟挂了。。。

后来听大神们一讲

只有3个数有用

左端点l 右端点r 与x轴交点x

x-l=r-x

不妨把边长直接作为x-l r-x

然后每次放在靠近x,y轴的地方再向右移动

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int m,a,b,c,d,ans;struct self{int x,y,l,r;} s[55]; void findcover(){ int a,b;double l,r; bool cover[55]={0}; for(a=1;a<=m;a++) { l=0;r=999999999; for(b=1;b
          
           l)l=s[b].r; for(b=a+1;b<=m;b++) if(s[b].l
           
            =r||l>=s[a].r||r<=s[a].l)cover[a]=1; } for(a=1;a<=m;a++)if(!cover[a])cout<
            <<" "; cout<<'\n';} int main(){ while(scanf("%d",&m)==1) { if(m==0)return 0; cin>>s[1].y; s[1].x=s[1].y; s[1].l=0; s[1].r=s[1].x*2; for(a=2;a<=m;a++) { scanf("%d",&s[a].y); for(b=1;b
             
              =s[b].y)s[a].x=max(s[a].x,s[b].x+s[b].y*2); else s[a].x=max(s[a].x,s[b].x+s[a].y*2); s[a].x=max(s[a].x,s[a].y); s[a].l=s[a].x-s[a].y; s[a].r=s[a].x+s[a].y; } findcover(); } return 0;}

转载地址：https://blog.csdn.net/li412302070/article/details/13005583 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：POJ 3063 Sherlock Holmes

下一篇：洛谷 1485 火枪打怪

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！