題目鏈接：點(diǎn)擊查看

題目大意：一共有 n 個人，進(jìn)行兩輪比賽，假設(shè)第一輪比賽的名次為 x ，第二輪的名次為 y ，那么這個人的得分為 x + y ，最后的排位會按照得分的非嚴(yán)格升序排列，有一個人在第一輪的名次為 x ，第二輪的名次為?y ，問這個人最終最好的名次和最差的名次分別是多少

題目分析：個人感覺難度大于C題的一道B題。。

參考視頻：https://www.bilibili.com/video/av91242850?p=2

需要注意好排位的標(biāo)準(zhǔn)是非嚴(yán)格升序，如果有三個人的得分相同，那么這三個人的排位都為并列第三，而非并列第一，首先要理解這里，正好說一下如何構(gòu)建最差的名次吧，接上面的話繼續(xù)來說，因?yàn)?n 個人總得分之和是不變的，所以我們只需要盡可能多的構(gòu)造與這個人的比分相同的分?jǐn)?shù)就好了，而不需要構(gòu)造比分比他小的分?jǐn)?shù)，因?yàn)闆]必要，最終效果都會讓這個人的排位往后靠，比如這個人的得分為 3 ，我們?nèi)绻胱屵@個人排位第三的話，1 2 3 和 3 3 3 的效果是一樣的，所以我們現(xiàn)在的目標(biāo)變?yōu)榱巳绾螛?gòu)造盡可能多的，分?jǐn)?shù)與 x + y 相同的分?jǐn)?shù)，假設(shè)此時(shí)第一輪的排名是升序的，為1,2,3...x+y-1，那么對應(yīng)著第二輪的分?jǐn)?shù)為 x+y-1,x+y-2...2,1，這樣能夠使得前面 x+y-1 個人的最終分?jǐn)?shù)都等于 x + y，也就是包含這個人在內(nèi)的x+y-1個人并列第 x + y - 1 ，這也是最壞情況了

再說回最好情況，也就是讓大于 x + y 的人盡可能多，分情況討論一下，如果 x + y <=n 時(shí)，我們可以讓第一輪的得分為1,2,3...n，而第二輪對應(yīng)的得分為n,n-1...2,1，這樣滿足每個人的得分都為?n + 1 ，而 x + y 因?yàn)樾∮诘扔?n ，所以肯定是排在第一名的，另一種情況就是 x + y > n 時(shí)，既然一定不能保證在第一名了，那么我們就讓第一名的那個人兩次排名之和盡可能小就好了，即讓一個人兩次都獲得第一名，此時(shí)我們可以忽略掉第一名的存在了，讓所有之前的排位都向前進(jìn)一位，也就是 x 變?yōu)榱?x - 1，y 變?yōu)榱?y - 1，n 變?yōu)榱?n - 1?，我們需要不斷重復(fù)這個步驟，直到回到第一種情況為止，假設(shè)需要一直操作 t 次，則當(dāng) x - t + y - t = n - t 時(shí)停止操作，可以解得 t = x + y - n ，也就是說有 x + y - n 個人會在這個人的前面，那么這個人最好的排位也就是 x + y - n + 1 了

記得維護(hù)一下邊界情況就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){LL n,x,y;scanf("%lld%lld%lld",&n,&x,&y);printf("%lld %lld\n",min(n,max(1LL,x+y-n+1)),min(x+y-1,n));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1313B Different Rules(数学+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。