題目傳送門

Chocolate Bunny

題目大意

求一個長度為n的數(shù)組
每次可以輸入兩個值i和j詢問，將會得到一個為$p_{i}mod{p}_j$返回值，最多可以進行2*n次詢問

思路

注意到詢問的最高次數(shù)為2*n次，所以每位最多在兩次詢問中確定
再注意到$p_{i}mod{p}_j$，聯(lián)想到小的值mod大的值為本身，所以可以通過不同方法詢問兩個值（即詢問i j和詢問j i），得到較小的那個值，通過這種方法將數(shù)組走一遍，每次tmp為當前未知的大值，小值記錄進數(shù)組，最后大值即為最大的n，將其放入數(shù)組即可

AC Code

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; #define endl '\n' #define INF 0x3f3f3f3f #define int long long // #define TDS_ACM_LOCAL const int N=2e5 +9; int n, a[N];void solve(){cin>>n;int tmp=1;for(int i=2; i<=n; i++){int q, p;cout<<"? "<<tmp<<" "<<i<<endl;cin>>q;cout<<"? "<<i<<" "<<tmp<<endl;cin>>p;if(q < p) a[i]=p;else a[tmp]=q, tmp=i;} a[tmp]=n;cout<<"!";for(int i=1; i<=n; i++) cout<<" "<<a[i];cout<<endl;return ; }signed main(){solve();return 0; }

總結

以上是生活随笔為你收集整理的C. Chocolate Bunny（思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

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