題意:幾個人想做好朋友,朋友之間相差位置小于等于k,且長度相同
分析;排序,將長度相同的放在一起。若長度相同,第i個人能放進去的條件是位置相差下雨等于k。
? ? ? ? 若不能放進去,將對頭踢掉,踢到對頭是第i個人的朋友的時候為止。若長度不相同,則將隊列清空。
? ? ? ? 更新sum值,在第i個人進去的時候就加上隊列的當前長度。
? ? ? ? 這個沒考慮的問題是當長度相同,但是隊列中的人都不符合其位置差,全部剔除的時候,第i個人卻沒有加進隊列,導致錯誤

// Problem#: 8842 // Submission#: 2269282 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ // All Copyright reserved by Informatic Lab of Sun Yat-sen University // Problem#: 8842 // Submission#: 2269196 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ // All Copyright reserved by Informatic Lab of Sun Yat-sen University /* #include<stdio.h> #include<string.h> const int MN=110; int vis[MN][MN]; char str[MN][MN]; int n,m; int A,B,C,D,E; int row[]= {-1,1,0,0}; int col[]= {0,0,-1,1}; int num1[200]; int num2[200]; struct Node { int x,y; } s,e; void DFS(int x,int y,char flag) { for(int i=0; i<4; i++) { int xx=x+row[i]; int yy=y+col[i]; if(xx>=1 && xx<=n && yy>=1 && yy<=m && str[xx][yy]!='X' && vis[xx][yy]==0) { if(str[xx][yy]==flag) { num2[flag]++; } } } } void work(int i,int j) { if(str[i][j]=='S') { s.x=i; s.y=j; } else if(str[i][j]=='G') { e.x=i; e.y=j; } num1[str[i][j]]++; } int main() { int i,j; while(scanf("%d%d",&n,&m)) { A=B=C=D=E=0; for(i=1; i<=n; i++) { scanf("%s",str[i]+1); for(j=1; j<=m; j++) { work(i,j); } } for(char t='a'; t<='e'; t++) { DFS(s.x,s.y,t); if(num2[t]==num1[t]) { DFS2() } } } return 0; } */ #include <stdio.h> #include <algorithm> #include < string .h> #include <queue> using namespace std; #define LL long long const int MN= 300010 ; struct Node { char nam[ 30 ]; int len; int pos; } node[MN]; queue < int > Q; bool cmp(Node a,Node b) { if (a.len!=b.len) return a.len< b.len; return a.pos< b.pos; } int main() { int n,k,i,j; int ans; while (scanf( " %d%d " ,&n,&k)!= EOF) { getchar(); while (! Q.empty()) Q.pop(); for (i= 1 ; i<=n; i++ ) { gets(node[i].nam); node[i].len = strlen(node[i].nam); node[i].pos = i; } sort(node + 1 ,node+n+ 1 ,cmp); long long sum= 0 ; int length= 1 ; Q.push( 1 ); int t; for (i= 2 ; i<=n; i++ ) { t = Q.front(); if (node[t].len!= node[i].len) { while (! Q.empty()) Q.pop(); length = 1 ; Q.push(i); } else { if (node[i].pos-node[t].pos<= k) { Q.push(i); sum += length; length ++ ; } else { while (! Q.empty()) { t = Q.front(); if (node[i].pos-node[t].pos<= k) { Q.push(i); sum += length; length ++ ; break ; } else { Q.pop(); length -- ; if (Q.empty()) { Q.push(i); length = 1 ; break ; } } } } } } printf( " %lld\n " ,sum); } return 0 ; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
