牛客練習賽75 D 減數(shù)游戲

思路:寫一下式子可以發(fā)每次選擇最小的兩個數(shù)進行操作，最后得到的答案會是最大的，那我們可以將它放進一個最小堆中來維護，但是里面的數(shù)是需要取模的，當它取模的時候，將會變小。那我們可以用一個隊列來維護，當它超過mod的時候就將它放入隊列中，因為是從最小堆中出來的，所以隊列中后面的數(shù)必然會大于前面的數(shù)，然后在隊列中循環(huán)操作就可以了。

代碼:

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=1e9+7; const ll N =1e6+10; const double eps = 1e-4; //const double pi=acos(-1); ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);} ll qk(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans; } ll n,k; ll p[N],hh=0,tt=0; void sovle(){priority_queue<ll,vector<ll>,greater<ll>> q;cin>>n>>k;for(int i=1;i<=n;i++){ll x;cin>>x;q.push(x);}queue<ll> w,w2;while(q.size()>1){ll t1=q.top();q.pop();ll t2=q.top();q.pop();ll k1=(t1*t2+k);if(k1>mod) p[tt++]=k1%mod;else q.push(k1);}if(q.size()){p[--hh]=q.top();}while(hh<tt-1){ll t1=p[hh++];ll t2=p[hh++];w2.push((t1*t2+k)%mod);}cout<<p[hh]%mod; } int main() {iosint t=1;// cin>>t;while(t--){sovle();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛75 D 减数游戏（队列优化（需要取模的）堆）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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