把半年前的blog重写一下,顺便熟悉一下这种考智商的博弈题。
题意:
N和K各有一堆石头,N知道两个人所有石头的重量,K只知道自己石头的重量,N选一个石头,把它的重量告诉K,如果是deceitful war, 这个told value就不一定是真实值,但是要保证,chose N>chose K if and only if told N>Told K(否则称天平时会露馅)并且told value!=K的任意一个石头的重量,如果是war,N的told value就是真实值把两个石头放在天平上称重,重的得一分。
对于War而言,因为N是先手,所以对于N取的每一个stone,K都会取一个最小的比它重的石头(if K has),如果K没有这样的石头存在,K lose 1 credit
对于Deceitful War,因为N可以谎报重量,所以N要用自己最轻的石头抵掉K最重的石头,所以从小到大遍历,如果N发现自己的某个石头比K的当前石子集合中最轻的石头重,那么N可以报一个很大的值,K所有stone都达不到这个值,所以K会选一个最轻的石头输给R以减小损失(K有更多重的石头最后的胜算才更大)。所以最后N剩下的都是轻的石头,和K的重的石头抵掉了。
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include <cmath> #include<algorithm> #include<stack> using namespace std; int T; int N; double na[1010]; double ke[1010]; int sn; int sk; int sn2; int sk2; void solve() { sn=0; sk=0; sn2=0; sk2=0; sort(na,na+N); sort(ke,ke+N); // for(int i=0;i<N;i++) // cout<<na[i]<<endl; //War int st=0; for(int i=0;i<N;i++) { for(int j=st;j<N;j++) { if(ke[j]>na[i]) { sk++; st=j+1; break; } } } // cout<<sk<<"++"<<endl; sn=N-sk; st=0; //D-War for(int i=0;i<N;i++)//Ke { for(int j=st;j<N;j++)//Na { if(na[j]>ke[i]) { sn2++; st=j+1; break; } } } } int main() { freopen("D-large.in","r",stdin); // freopen("input.txt","r",stdin); freopen("d-large.out","w",stdout); scanf("%d",&T); for(int i=1;i<=T;i++) { scanf("%d",&N); for(int i=0;i<N;i++) scanf("%lf",&na[i]); for(int i=0;i<N;i++) scanf("%lf",&ke[i]); solve(); printf("Case #%d: %d %d\n",i,sn2,sn); } return 0; }