钢材技术支持东莞网站建设,专业制作网站价格,天津餐饮网站建设,鑫瀚通网站建设problem
洛谷链接
solution
田忌赛马孪生兄弟。
浙江选手最坏情况就是外省最好情况#xff0c;所以本质上两个子问题是同一个做法。
相信所有人都是读完题后就有田忌赛马的思想了。#xff08;如果还没上过小学语文课的当我没说#xff09;
实力强的去虐实力菜的…problem
洛谷链接
solution
田忌赛马孪生兄弟。
浙江选手最坏情况就是外省最好情况所以本质上两个子问题是同一个做法。
相信所有人都是读完题后就有田忌赛马的思想了。如果还没上过小学语文课的当我没说
实力强的去虐实力菜的而且为了自己队友实力考虑肯定是把比自己菜的对手当中最强的整死。 假设两组实力相当的比赛得分是 222那么自己实力强的虐对方实力弱的自己实力弱的送给对方实力强的虐得分也是 222。所以这种打实力差的方式是不劣的。 但是这只是对于一个人的实力而言的最优方式。
因为平局的可能性我们还需要统筹安排是哪个实力先出战。
在上述虐菜的前提下我们还要尽可能地保留实力更强者和外省的更强实力再一绝高下。
给一组数据帮助理解
2 4 10 10 10 9
1 3 5 7 8 9
最好得分:1-2 3-4 9-9 5
所以不能先从实力强的开始去找菜鸡对手所以我们应当按照实力从低到高匹配对手。
如果当前这名选手没有比他更菜的对手最多可能有实力相当的对手就暂时跳过。
最后剩下的若干名实力要么就是比对方菜的要么就是实力相当的。
这时候再来统计平局的分数。
不能将平局和虐菜放在一起原因类似的有可能后面某个实力强的队友只能虐现在这个和自己实力相当的对手那肯定是牺牲自己平局分数换取队友获胜分数。
给一组数据
1 3
1 10
最好得分2在考场上我的实现略丑但本质是一样的。
时间复杂度 O(nlogn)O(n\log n)O(nlogn)如果写个基排就能做到 O(n)O(n)O(n)。
应该不会有丝箔卡 log\loglog 吧 …\dots…
code
#include bits/stdc.h
using namespace std;
#define maxn 100005
int n, ans1, ans2;
bool vis[maxn];
int w1[maxn], w2[maxn];
multiset int s;int main() {scanf( %d, n );for( int i 1;i n;i ) scanf( %d, w1[i] );for( int i 1;i n;i ) scanf( %d, w2[i] );sort( w1 1, w1 n 1 );for( int i 1;i n;i ) s.insert( w2[i] );for( int i 1;i n;i ) {auto it s.lower_bound( w1[i] ); vis[i] 1;if( it s.begin() ) { vis[i] 0; continue; }else -- it, s.erase( it ), ans1 2;}for( int i n;i;i -- )if( ! vis[i] ) {if( *s.begin() w1[i] ) ans1 ;s.erase( s.begin() );}sort( w2 1, w2 n 1 );for( int i 1;i n;i ) vis[i] 0, s.insert( w1[i] );for( int i 1;i n;i ) {auto it s.lower_bound( w2[i] ); vis[i] 1;if( it s.begin() ) { vis[i] 0; continue; }else -- it, s.erase( it );}for( int i n;i;i -- )if( ! vis[i] ) {if( *s.begin() w2[i] ) ans2 ;else ans2 2;s.erase( s.begin() );}printf( %d %d, ans1, ans2 );return 0;
}#include bits/stdc.h
using namespace std;
#define maxn 100005
int n;
int w1[maxn], w2[maxn];int solve( int w1[], int w2[] ) {int ans 0, l1 1, l2 1, r1 n, r2 n;while( l1 r1 and l2 r2 ) {if( w1[l1] w2[l2] ) ans 2, l1 , l2 ;else if( w1[r1] w2[r2] ) ans 2, r1 --, r2 --;else ans w1[l1] w2[r2], l1 , r2 --;}return ans;
}int main() {scanf( %d, n );for( int i 1;i n;i ) scanf( %d, w1[i] );for( int i 1;i n;i ) scanf( %d, w2[i] );sort( w1 1, w1 n 1 );sort( w2 1, w2 n 1 );printf( %d %d\n, solve( w1, w2 ), (n 1) - solve( w2, w1 ) );return 0;
}
