「NOIP模拟赛」舞蹈课
问题描述
有n个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果相差最小的不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为ABCD，那么BC出列之后队伍变为AD）。舞蹈技术相差最小即是的绝对值最小。
你的任务是，模拟以上过程，确定跳舞的配对及顺序。
输入
第一行为正整数n<=200000：队伍中的人数。下一行包含n个字符B或者G，B代表男，G代表女。下一行为n个整数ai<=10^7。所有信息按照从左到右的顺序给出。在50%的数据中，n<=200。
输出
第一行：出列的总对数k。接下来输出k行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右1至n编号）。请先输出较小的整数，再输出较大的整数。
样例输入
4
BGBG
4 2 4 3
样例输出
2
3 4
1 2
样例输入
4
BGBB
1 1 2 3
样例输出
1
1 2
题解
直接暴力有50分。。。
每次用for找最小值，然后标记一下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #include<queue> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int 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; } int n,ans; int a[200005],a1[200005],a2[200005]; char ch[200005]; bool mark[200005]; int next(int x) { for(int i=x+1;i<=n;i++) if(!mark[i]) { if(ch[x]!=ch[i])return i; else return -1; } return -1; } void solve() { int mn,t1,t2; while(1) { mn=inf,t1=-1; for(int i=1;i<=n;i++) if(!mark[i]) { int to=next(i); if(to==-1)continue; if(abs(a[to]-a[i])<mn) { mn=abs(a[to]-a[i]); t1=i;t2=to; } } if(t1==-1)return; a1[++ans]=t1;a2[ans]=t2; mark[t1]=mark[t2]=1; } } int main() { n=read(); scanf("%s",ch+1); for(int i=1;i<=n;i++)a[i]=read(); solve(); printf("%d\n",ans); for(int i=1;i<=ans;i++) printf("%d %d\n",a1[i],a2[i]); return 0; } |
100分做法直接搞个堆找最小值。。然后用链表维护删除即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #include<queue> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int 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; } int n,ans; int a[200005],next[200005],pre[200005],a1[200005],a2[200005]; char ch[200005]; bool mark[200005]; struct data{int val,pos;}; inline bool operator>(data a,data b) { return a.val>b.val||(a.val==b.val&&a.pos>b.pos); } void solve() { priority_queue<data,vector<data>,greater<data> >q; for(int i=1;i<n;i++) if(ch[i]!=ch[i+1]) q.push((data){abs(a[i]-a[i+1]),i}); while(!q.empty()) { int mn=q.top().val,now=q.top().pos;q.pop(); int l=pre[now],t=next[now],r=next[t]; if(mark[now]||mark[t])continue; if(abs(a[now]-a[t])!=mn||ch[now]==ch[t])continue; mark[now]=mark[t]=1; a1[++ans]=now;a2[ans]=t; if(l&&r&&ch[r]!=ch[l]) { q.push((data){abs(a[r]-a[l]),l}); } next[l]=r;pre[r]=l; } printf("%d\n",ans); for(int i=1;i<=ans;i++) printf("%d %d\n",a1[i],a2[i]); } int main() { //freopen("dancingLessons.in","r",stdin); //freopen("dancingLessons.out","w",stdout); n=read();mark[0]=1; scanf("%s",ch+1); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<n;i++)next[i]=i+1; for(int i=2;i<=n;i++)pre[i]=i-1; solve(); return 0; } |
Subscribe
计数器 9301115
OI 课件=>
OI 课件=>