{"id":256,"date":"2010-05-21T15:43:00","date_gmt":"2010-05-21T07:43:00","guid":{"rendered":"http:\/\/localhost\/?p=256"},"modified":"2010-05-21T15:43:00","modified_gmt":"2010-05-21T07:43:00","slug":"baltic2008gloves","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=256","title":{"rendered":"[Baltic2008]Gloves"},"content":{"rendered":"\n

[Baltic2008]Gloves<\/p>\n

Time Limit:10000MS Memory Limit:165536K
Total Submit:43 Accepted:16
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

\u624b\u5957\u88ab\u653e\u5728\u4e86\u4e24\u4e2a\u62bd\u5c49\u91cc, \u6240\u6709\u7684\u5de6\u624b\u5957\u653e\u5728\u5de6\u8fb9\u7684\u62bd\u5c49\u91cc, \u6240\u6709\u7684\u53f3\u624b\u5957\u653e\u5728\u53f3\u8fb9\u7684\u62bd\u5c49\u91cc\uff0e
\u624b\u5957\u4e00\u5171\u6709N\u79cd\u989c\u8272, \u5df2\u77e5\u4e24\u4e2a\u62bd\u5c49\u6bcf\u79cd\u989c\u8272\u7684\u624b\u5957\u5404\u6709\u591a\u5c11\u53ea, \u5982\u679c\u968f\u4fbf\u5728\u5de6\u8fb9\u62ff\u4e00\u53ea, \u53f3\u8fb9\u62ff\u4e00\u53ea
\u5f88\u53ef\u80fd\u4f1a\u9020\u6210\u62ff\u5230\u4e00\u53ea\u7ea2\u8272\u7684\u5de6\u624b\u5957\u548c\u4e00\u53ea\u84dd\u8272\u53f3\u624b\u5957… \u73b0\u60f3\u77e5\u9053\u5e94\u8be5\u4ece\u5de6\u8fb9\u7684\u62bd\u5c49\u53d6\u51fa\u591a\u5c11\u53ea\u5de6\u624b\u5957(\u8bbe\u4e3ax)
\u53f3\u8fb9\u7684\u62bd\u5c49\u53d6\u51fa\u591a\u5c11\u53ea\u53f3\u624b\u5957(\u8bbe\u4e3ay), \u6ee1\u8db3\u81f3\u5c11\u53ef\u4ee5\u627e\u5230\u4e00\u5bf9\u5339\u914d\u7684\u624b\u5957(\u5373\u989c\u8272\u76f8\u540c), \u5e76\u4e14x + y\u6700\u5c0f
\u5982\u679c\u6709\u591a\u4e2a(x, y)\u6ee1\u8db3x + y\u6700\u5c0f, \u4f60\u5e0c\u671b\u6ee1\u8db3x\u5c3d\u53ef\u80fd\u7684\u5c0f
\u4e0d\u59a8\u8bbe \u6bcf\u4e2a\u62bd\u5c49\u91cc\u6bcf\u53ea\u624b\u5957\u88ab\u53d6\u51fa\u7684\u6982\u7387\u662f\u7b49\u4ef7\u7684\uff0e
\u8f93\u5165\u6587\u4ef6
\u8f93\u5165\u6587\u4ef6\u7b2c\u4e00\u884c\u4e2d\u6709\u4e00\u4e2a\u6b63\u6574\u6570N,\u8868\u793a\u989c\u8272\u7684\u79cd\u6570\uff0e
\u7b2c\u4e8c\u884c\u6709N\u4e2a\u975e\u8d1f\u6574\u6570, \u8868\u793a\u5de6\u62bd\u5c49\u4e2d\u6bcf\u79cd\u989c\u8272\u7684\u5de6\u624b\u5957\u7684\u4e2a\u6570\uff0e
\u7b2c\u4e09\u884c\u6709N\u4e2a\u975e\u8d1f\u6574\u6570, \u8868\u793a\u53f3\u62bd\u5c49\u4e2d\u6bcf\u79cd\u989c\u8272\u7684\u53f3\u624b\u5957\u7684\u4e2a\u6570\uff0e
\u8f93\u51fa\u6587\u4ef6
\u4f60\u9700\u8981\u8f93\u51fa\u6ee1\u8db3\u9898\u76ee\u6761\u4ef6\u7684(x, y)\uff0e<\/p>\n

Input <\/strong><\/p>\n

\u8f93\u5165\u6587\u4ef6\u7b2c\u4e00\u884c\u4e2d\u6709\u4e00\u4e2a\u6b63\u6574\u6570N,\u8868\u793a\u989c\u8272\u7684\u79cd\u6570\uff0e
\u7b2c\u4e8c\u884c\u6709N\u4e2a\u975e\u8d1f\u6574\u6570, \u8868\u793a\u5de6\u62bd\u5c49\u4e2d\u6bcf\u79cd\u989c\u8272\u7684\u5de6\u624b\u5957\u7684\u4e2a\u6570\uff0e
\u7b2c\u4e09\u884c\u6709N\u4e2a\u975e\u8d1f\u6574\u6570, \u8868\u793a\u53f3\u62bd\u5c49\u4e2d\u6bcf\u79cd\u989c\u8272\u7684\u53f3\u624b\u5957\u7684\u4e2a\u6570\uff0e <\/p>\n

Output <\/strong><\/p>\n

\u8f93\u51fa\u6ee1\u8db3\u9898\u76ee\u6761\u4ef6\u7684(x, y)\uff0e<\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Source
\u997f\u3002\u3002\u6211\u7684\u7b97\u6cd5\u8d85\u7ea7\u6162\uff0c\u8fd0\u884c\u4e86\u63a5\u8fd16000MS\u56e7\u3002\u3002\u3002
\u8fd9\u9053\u9898\u8fd8\u662f\u6709\u70b9\u610f\u601d\u7684\uff0c\u4e00\u5f00\u59cb\u6211\u6ca1\u4ec0\u4e48\u60f3\u6cd5\uff0c\u7136\u540e\u6ce8\u610f\u5c06\u8fd9\u4e2aN\u4e2a\u989c\u8272\u5212\u5206\u62102\u90e8\u5206\uff0c\u4e00\u79cd\u5de6\u624b\u5957\u8bbe\u548c\u4e3aL\uff0c\u4e00\u79cd\u53f3\u624b\u5957\uff0c\u8bbe\u548c\u4e3aR\uff0c\u90a3\u4e48\u5bf9\u4e8e\u4efb\u4f55x<=L&&y<=R\u7684\u90fd\u5c06\u4e0d\u884c\u3002\u3002\u4e8e\u662f\u679a\u4e3e\u6240\u6709\u7684\u5212\u5206\uff081<<n\uff09\u3002\u3002\u7b97\u51fa\u6bcf\u79cd\u7ea6\u675f\uff0c\u628a\u6240\u6709\u7ea6\u675f\u770b\u6210\u70b9\uff0c\u7136\u540e\u53bb\u6389\u88ab\u5305\u542b\u7684\u70b9\uff0c\u7136\u540e\u6309X\u6392\u5e8f\uff0c\u90a3\u4e48\u7b54\u6848\u53ea\u53ef\u80fd\u51fa\u73b0\u5728\u4e24\u4e2a\u76f8\u90bb\u7684\u70b9\u7ec4\u6210\u7684\u77e9\u5f62\u7684\u5de6\u4e0b\u89d2\u7684\u53f3\u4e0a\u4e00\u683c\u3002\u3002\u5f88\u597d\u8bc1\u660e\u5c31\u4e0d\u591a\u8bf4\u4e86\u3002\u3002
Code\uff1a
<\/strong><\/p>\n

#include<iostream>#include<algorithm>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=20;typedef long long ll;const ll inf=1LL<<60;int A[maxn],B[maxn],n,m=0;ll L=0,R=0;struct Point{ ll x,y; Point(){} Point(ll _x,ll _y):x(_x),y(_y){} bool operator<(const Point&o)const { if(x!=o.x)return x<o.x; return y<o.y; }}P[1<<maxn];void Dfs(int p,ll l,ll r){ if(p==n){P[m++]=Point(l,r);return;} Dfs(p+1,l+A[p],r);Dfs(p+1,l,r+B[p]);}int main(){ \/\/freopen("in","r",stdin); cin>>n;rep(i,n)cin>>A[i],L+=A[i];rep(i,n)cin>>B[i],R+=B[i]; Dfs(0,0,0);sort(P,P+m);int p=0;ll l=inf,r=inf; for(int i=0;i<m;i++) { while(p&&P[p-1].y<=P[i].y)p–; P[p++]=P[i]; } m=p; for(int i=0;i<m-1;i++) { ll a=P[i].x+1,b=P[i+1].y+1; if(!(a<=L&&b<=R))continue; if(a+b>l+r)continue; if(a+b<l+r)l=a,r=b; else if(a<l)l=a,r=b; } cout<<l<<" "<<r<<endl;}2 8100%\u7684\u6d4b\u8bd5\u6570\u636e, N <= 20, 0 <= ai, bi <= 108\uff0e40 7 1 61 5 0 6 <\/p>\n","protected":false},"excerpt":{"rendered":"

[Baltic2008]Gloves Time Limit:10000MS Memory Limit:165536KTotal Submit:43 Accepted:16 Case Time Limit:1000MS Description \u624b\u5957\u88ab\u653e\u5728\u4e86\u4e24\u4e2a\u62bd\u5c49\u91cc, \u6240\u6709\u7684\u5de6\u624b\u5957\u653e\u5728\u5de6\u8fb9\u7684\u62bd\u5c49\u91cc, \u6240\u6709\u7684\u53f3\u624b\u5957\u653e\u5728\u53f3\u8fb9\u7684\u62bd\u5c49\u91cc\uff0e \u624b\u5957\u4e00\u5171\u6709N\u79cd\u989c\u8272, \u5df2\u77e5\u4e24\u4e2a\u62bd\u5c49\u6bcf\u79cd\u989c\u8272\u7684\u624b\u5957\u5404\u6709\u591a\u5c11\u53ea, \u5982\u679c\u968f\u4fbf\u5728\u5de6\u8fb9\u62ff\u4e00\u53ea, \u53f3\u8fb9\u62ff\u4e00\u53ea \u5f88\u53ef\u80fd\u4f1a\u9020\u6210\u62ff\u5230\u4e00\u53ea\u7ea2\u8272\u7684\u5de6\u624b\u5957\u548c\u4e00\u53ea\u84dd\u8272\u53f3\u624b\u5957… \u73b0\u60f3\u77e5\u9053\u5e94\u8be5\u4ece\u5de6\u8fb9\u7684\u62bd\u5c49\u53d6\u51fa\u591a\u5c11\u53ea\u5de6\u624b\u5957(\u8bbe\u4e3ax) \u53f3\u8fb9\u7684\u62bd\u5c49\u53d6\u51fa\u591a\u5c11\u53ea\u53f3\u624b\u5957(\u8bbe\u4e3ay), \u6ee1\u8db3\u81f3\u5c11\u53ef\u4ee5\u627e\u5230\u4e00\u5bf9\u5339\u914d\u7684\u624b\u5957(\u5373\u989c\u8272\u76f8\u540c), \u5e76\u4e14x + y\u6700\u5c0f \u5982\u679c\u6709\u591a\u4e2a(x, y)\u6ee1\u8db3x + y\u6700\u5c0f, \u4f60\u5e0c\u671b\u6ee1\u8db3x\u5c3d\u53ef\u80fd\u7684\u5c0f \u4e0d\u59a8\u8bbe \u6bcf\u4e2a\u62bd\u5c49\u91cc\u6bcf\u53ea\u624b\u5957\u88ab\u53d6\u51fa\u7684\u6982\u7387\u662f\u7b49\u4ef7\u7684\uff0e \u8f93\u5165\u6587\u4ef6 \u8f93\u5165\u6587\u4ef6\u7b2c\u4e00\u884c\u4e2d\u6709\u4e00\u4e2a\u6b63\u6574\u6570N,\u8868\u793a\u989c\u8272\u7684\u79cd\u6570\uff0e \u7b2c\u4e8c\u884c\u6709N\u4e2a\u975e\u8d1f\u6574\u6570, \u8868\u793a\u5de6\u62bd\u5c49\u4e2d\u6bcf\u79cd\u989c\u8272\u7684\u5de6\u624b\u5957\u7684\u4e2a\u6570\uff0e \u7b2c\u4e09\u884c\u6709N\u4e2a\u975e\u8d1f\u6574\u6570, \u8868\u793a\u53f3\u62bd\u5c49\u4e2d\u6bcf\u79cd\u989c\u8272\u7684\u53f3\u624b\u5957\u7684\u4e2a\u6570\uff0e \u8f93\u51fa\u6587\u4ef6 \u4f60\u9700\u8981\u8f93\u51fa\u6ee1\u8db3\u9898\u76ee\u6761\u4ef6\u7684(x, y)\uff0e Input \u8f93\u5165\u6587\u4ef6\u7b2c\u4e00\u884c\u4e2d\u6709\u4e00\u4e2a\u6b63\u6574\u6570N,\u8868\u793a\u989c\u8272\u7684\u79cd\u6570\uff0e \u7b2c\u4e8c\u884c\u6709N\u4e2a\u975e\u8d1f\u6574\u6570, \u8868\u793a\u5de6\u62bd\u5c49\u4e2d\u6bcf\u79cd\u989c\u8272\u7684\u5de6\u624b\u5957\u7684\u4e2a\u6570\uff0e \u7b2c\u4e09\u884c\u6709N\u4e2a\u975e\u8d1f\u6574\u6570, \u8868\u793a\u53f3\u62bd\u5c49\u4e2d\u6bcf\u79cd\u989c\u8272\u7684\u53f3\u624b\u5957\u7684\u4e2a\u6570\uff0e Output \u8f93\u51fa\u6ee1\u8db3\u9898\u76ee\u6761\u4ef6\u7684(x, y)\uff0e Sample Input Sample Output Source […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/256"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=256"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/256\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}