本文共 1332 字，大约阅读时间需要 4 分钟。
题目要求给出两种策略：
1，田忌要尽可能少输 2，田忌要尽可能多赢无非就是改变赢局和平局的比例。
当尽可能少输时，那就要先采取平局，然后再尽量取胜，剩下就是必输了。
当尽可能多赢时，那就要先尽量取胜，然后尽量平局，剩下就是必输了。
枚举时暴力做的，可能比最优双端队列贪心要慢。
// ShellDawn// Codeforces 777B// No.34#include#include #include #include #include #include #define MM(x,y) memset(x,y,sizeof(x))#define INF 0x3f3f3f3f#define LL long longusing namespace std;//#define maxn 1005int N;int VA[maxn];int VB[maxn];int A[maxn];int B[maxn];int ans = 0;int res = 0;void equal(){ int L = 1, R = 1; while( L <= N && R<=N){ while(VA[L] == 1) L++; while(VB[R] == 1) R++; if(L > N || R > N) break; if(A[L] > B[R]) R++; else if(A[L] < B[R]) L++; else{ //printf("<%d %d> (等于) <%d %d>\n",L,A[L],R,B[R]); VA[L] = VB[R] = 1; res ++ ; } }}void win(){ for(int i=1;i<=N;i++){ if(VA[i] == 1) continue; for(int j=N;j>=1;j--){ if(VB[j] == 0 && A[i] > B[j]){ //printf("<%d %d> (大于) <%d %d>\n",i,A[i],j,B[j]); VA[i] = 1; ans++; VB[j] = 1; break; } } }}int main(){ scanf("%d",&N); getchar(); for(int i=1;i<=N;i++){ char c = getchar(); B[i] = c - '0'; } getchar(); for(int i=1;i<=N;i++){ char c = getchar(); A[i] = c - '0'; } sort(A+1,A+N+1); sort(B+1,B+N+1); MM(VA,0); MM(VB,0); ans = 0; res = 0; equal(); win(); printf("%d\n",N-ans-res); MM(VA,0); MM(VB,0); ans = 0; res = 0; win(); equal(); printf("%d\n",ans); return 0;}
转载地址：http://pnwji.baihongyu.com/