3983: [WF2012]Takeover Wars
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 73 Solved: 27
[Submit][Status][Discuss]
Description
你正在学习一个两个公司间的商业战争，它们分别是X和Y（译者注：原文名称太复杂，这里简记).每一个公司包含一系列的子公司。这次战争可以看做是市场战争，X有n个子公司而Y有m个子公司(1<=n,m<=10^5)，你知道每个子公司的市场价值。
每个子公司可以决定一个子公司来进行一次交易，交易既可以是友好的，也可以是敌对的。一个友好的交易意味着同属于一个公司子公司和子公司之间的合并。一次合并产生的新的子公司的市场价值是参与交易双方的价值之和。一次友好交易中，子公司的大小没有限制。
一个敌对的交易意味着一个子公司A（既可以是X也可以是Y)希望和子公司B交易。为了让交易顺利进行，A的市场价值必须大于B的。这样做之后，B从市场上消失，A的市场价值不变。为了简化问题,我们可以认为，所有的操作序列不会出现相同价值的子公司间的交易。
公司轮流行动，X先动。一个公司什么都不做当且仅当它什么都不能做。如果一个公司的是子公司全没了，那么它就输掉了这场商业竞争。
你的目标算出哪个公司一定能赢得胜利。在样例一中，X公司可以用7-价值公司干掉Y的一个子公司。然后Y只能干掉X的一个1-价值公司，然后Y的最后一个公司就被干掉了。在样例二中，X公司一开始只能合并它的两个公司变为6-价值公司，Y此时应该用友好操作合并2个5-价值公司为10-价值公司。X就只能继续合并,但无论它怎么合并，都会被Y的10-公司吃掉一个，然后X只能pass，Y就再吃一个，就取胜了。
Input
每个测试数据包含三行。第一行两个数n,m表示X和Y的子公司数。第二行n个数描述X的子公司价值（用空格隔开），第三行m个数描述Y的子公司价值（用空格隔开）(价值<=10^12)。
Output
对于每组数据，先输出测试数据组号，若X胜利，输出"Takeover Incorporated"，否则输出"Buyout Limited"。（译者注：其实这就是那个很复杂的名字。)
Sample Input
3 2
7 1 1
5 5
4 2
3 3 3 3
5 5
7 1 1
5 5
4 2
3 3 3 3
5 5
Sample Output
Case 1: Takeover Incorporated
Case 2: Buyout Limited
Case 2: Buyout Limited
拍了半天没拍出来发现有个地方没开long long
#include <cstdio>
#include <algorithm>
using namespace std;
long long a[2][100005],b,c,d,e,f,g,h,i,j,k,l,m,n[2];
int main(){
int Case=0;while(scanf("%lld%lld",&n[0],&n[1])!=EOF){
Case++;g=0;
printf("Case %d: ",Case);
for(i=1;i<=n[0];i++)scanf("%lld",&a[0][i]);
for(i=1;i<=n[1];i++)scanf("%lld",&a[1][i]);
sort(a[0]+1,a[0]+1+n[0]);
sort(a[1]+1,a[1]+1+n[1]);
for(long long N0=n[0],N1=n[1],s0=0,s1=0;N0&&N1;N0--,N1--){
s0=s0+a[0][N0];
if(s0<s1)break;
s1=s1+a[1][N1];
if(N0<n[0]&&s0>s1){g=1;}
}
if(g){printf("Takeover Incorporated\n");continue;}
for(k=0;n[0]&&n[1];k^=1){
long long X1=a[k][n[k]],X2=a[k][n[k]-1],Y1=a[k^1][n[k^1]],Y2=a[k^1][n[k^1]-1];
if(n[k^1]==1){
if(X1>Y1){n[k^1]--;continue;}
if(n[k]==1&&X1==Y1)break;
}
else{
if(X1+X2<=Y1+Y2){
if(Y1+Y2<=X1){n[k^1]--;continue;}
if(X1>Y1&&Y2+a[k^1][n[k^1]-2]<=X1+X2){n[k^1]--;continue;}
}
}
if(n[k]==1)continue;
a[k][--n[k]]=X1+X2;
}
if(!n[1])printf("Takeover Incorporated\n");
else printf("Buyout Limited\n");
}
return 0;
}
2023年1月12日 13:23
In the world of business, takeover wars are not uncommon. Two or more companies may compete for control of another company by buying up its shares on the open market. The company that ends up with the most LA Homeless Crisis shares is the one that wins the war. Takeover wars can be friendly or hostile. In a friendly takeover, the companies involved may negotiate terms before any shares are bought. In a hostile takeover, the companies involved may not be on good terms, and the takeover may be unsolicited.