题解|#C. Jumping on Tiles# codeforces 820

说实话，这道题卡的最久的就是一直在由于1s钟这种暴力会不会超时的问题，还是不太自信，这个题既想走的路径短，又想走的步数最多，那就按着字母顺序走呗。

以logic为例

在字母表中的顺序是这样的 c g i l，所以要想从l走到c路径最短且步数最多，就是l->i->g->c，知道这点之后，这道题就容易了。

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
struct node{
	int val;
	int pos;
	node(int a,int b){
		val=a; pos=b;
	}
	node(){
	}
	bool operator<(const node&p) const{
		return val<p.val;
	}
}ans[M]; 
int a[M];
int main(){
    int t; cin>>t;
    while(t--){
    	string s; cin>>s;
    	int n=s.size();
    	for(int i=1;i<=s.size();i++){
    		a[i]=s[i-1]-'0';
		}
		if(a[1]>a[n]){
			for(int i=1;i<=n;i++){
				a[i]=-a[i];
			}
		}
		int tot=0;
		for(int i=2;i<n;i++){
			if(a[i]>=a[1]&&a[i]<=a[n]){
				ans[++tot].val=a[i];
				ans[tot].pos=i;
			} 
		}
		sort(ans+1,ans+1+tot);
		cout<<abs(a[1]-a[n])<<" "<<tot+2<<endl;
		cout<<"1"<<" ";
		for(int i=1;i<=tot;i++){
			cout<<ans[i].pos<<" ";
		}
		cout<<n<<endl;
	}
	return 0;
}