hdu 5233 Gunner II 離散化

2019-11-06 06:22:41

字體：大中小

來源：轉載

供稿：網友

題目鏈接:

http://acm.hdu.edu.cn/showPRoblem.php?pid=5233

題意:

有n只鳥，還有n棵樹。第i只鳥站在第i棵樹的頂端。這些樹從左到右排成一條直線。每一棵樹都有它的高度。Jack站在最左邊那棵樹的左邊。當Jack在高度為H的地方向右發射一棵子彈時，站在高度為H的樹上且離Jack最近的鳥兒就會落下來。 Jack會射擊多次，他想知道每次射擊哪只鳥兒會落下來。

題解:

離散化

代碼:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 2e5+10;struct node{ int x,id;}h[maxn];vector<int> k,dp[maxn];map<int,int> H;int q[maxn],cnt[maxn];void init(){ MS(h); MS(q); MS(cnt); H.clear(); k.clear(); for(int i=0; i<maxn; i++) dp[i].clear();}int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ init(); for(int i=0; i<n; i++){ h[i].x = read(); h[i].id = i+1; k.push_back(h[i].x); } for(int i=0; i<m; i++){ q[i] = read(); k.push_back(q[i]); } sort(k.begin(),k.end()); k.erase(unique(k.begin(),k.end()),k.end()); for(int i=0; i<(int)k.size(); i++){ H[k[i]] = i; } for(int i=0; i<n; i++) dp[H[h[i].x]].push_back(h[i].id); for(int i=0; i<m; i++){ if(cnt[H[q[i]]] >= (int)dp[H[q[i]]].size()) cout << -1 << endl; else{ cout << dp[H[q[i]]][cnt[H[q[i]]]] << endl; cnt[H[q[i]]]++; } } } return 0;}

上一篇：Thread-synchronized同步 -火車票實例

下一篇：IC項目，門級代碼的工藝庫移植