首页 > B题
头像
lczk
发布于 2021-05-04 10:00
+ 关注

B题

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 10005;

struct Node{
	int w;
	int h;
}; 
Node a[N];
int b[N]; 

bool cmp(const Node &a,const Node &b){
    if(a.h==b.h){
        return a.w>b.w;
    }
    else{
        return a.h>b.h;
    }
	
}

int main(){
	int n,x,y,ans,an,max,sum,ma,lt,tot_w;
    lt = 0;
	cin>>n>>x>>y;
    
    memset(b,0,sizeof(b));
    
    ma = 0;
    tot_w=0;
	for(int i=1;i<=n;i++){
		cin>>a[i].w>>a[i].h;
        tot_w+=a[i].w;
        if(a[i].h>ma){
            ma = a[i].h;
         }
		if(a[i].w>x||a[i].h>y){
           lt=1;
        }
	}
	if(lt==1){
        cout<<"impossible"<<endl;
        return 0;
    }
    

	sort(a+1,a+n+1,cmp);
	
/*	for(int i=1;i<=n;i++){
		cout<<a[i].h<<" "<<a[i].w<<endl;
	}
	*/
	sum = 0;
	max = 0;
	an = 0;
	ans = 1; 
	for(int i=1;i<=n;i++){
        if(b[i]==1){
            continue;
        }
		sum+=a[i].w;
		
		if(sum>x){
            sum = sum -a[i].w;
            for(int j=i+1;j<=n;j++){
			    
                if(sum+a[j].w<=x&&b[j]!=1){
                //	cout<<"-1"<<endl;
                    sum += a[j].w;
                    if(a[j].h>max){
                        max = a[j].h;
                    }
                    b[j] = 1;
                }
            }
            
           // cout<<sum-a[i].w<<endl;
			sum = a[i].w;
		//	cout<<sum<<endl;
			//ma = max;
			an += max;
			max = a[i].h;
			ans++;
		}
        if(a[i].h>max){
			max = a[i].h;
		}
	}
    //cout<<an<<endl;
    an+=max;
 //   cout<<an<<endl;
 //	cout<<ans<<" "<<an<<endl;
	if(ans>2||an>y){
		cout<<"impossible"<<endl;
	}
	else{
		if(ans==1){
            if(ma==y){
                cout<<"-1"<<endl;
            }
            else{
                cout<<an<<endl;
            }
			
		}
		else{
			cout<<ma<<endl;
		}
	}
	return 0;
}
我的做法有什么地方没有考虑到 为什么总是差一点过,求大佬解答!

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

热门推荐