题目描述

小 R 有一个长度为 L 的字符串 S=s1​…sL​，其中只包含小写英文字母。小 R 发现，虽然 S 可能很长，但它可以分成 n 个连续的段，其中第 i (1≤i≤n) 段由 ai​ 个小写英文字母 ci​ 构成。把这 n 段依次拼接起来便得到 S，因此 L=∑i=1n​ai​。相邻两段中的字符可以相同。

小 X 喜欢回文串。若一个字符串反转后与原字符串相同，就称它是回文串，例如 aba、abba 都是回文串，而 aabbc 不是。也就是说，字符串 S 是回文串，当且仅当对于所有 i (1≤i≤L)，均有 si​=sL+1−i​。

小 X 想让小 R 把 S 改成回文串。小 R 可以将 S 中任意一个位置的字符修改成任意小写英文字母。他想用尽量少的修改满足小 X 的要求。

你需要帮助小 R 求出，他最少需要修改多少个位置的字符，才能将 S 改成回文串。

输入格式

从文件 string.in 中读入数据。

输入的第一行包含一个正整数 n。

输入的第 i+1 (1≤i≤n) 行包含一个正整数 ai​ 和一个小写英文字母 ci​。

输出格式

输出到文件 string.out 中。

输出一行一个整数，表示小 R 最少需要修改多少个位置的字符，才能将 S 改成回文串。

输入输出样例

输入 #1复制

3
2 a
2 b
1 c

输出 #1复制

2

输入 #2复制

2
2 a
3 a

输出 #2复制

0

输入 #3复制

6
1000000000 a
1000000000 a
1000000000 a
1000000000 b
1000000000 b
1000000000 b

输出 #3复制

3000000000

说明/提示

样例 1 解释

小 R 的字符串 S 由 3 段构成：第 1 段由 2 个 a 组成，第 2 段由 2 个 b 组成，第 3 段由 1 个 c 组成，依次拼接得到 S=aabbc。

小 R 可以将最后一个字符 c 和倒数第二个字符 b 都改为 a，得到回文串 aabaa，共修改 2 个位置的字符。可以证明，小 R 最少需要修改 2 个位置的字符，才能将 S 改成回文串。

样例 2 解释

小 R 的字符串 S 由 2 段构成：第 1 段由 2 个 a 组成，第 2 段由 3 个 a 组成，依次拼接得到 S=aaaaa，则 S 已经是回文串，不需要修改。

样例 4

见题目目录下的 string/4.in 与 string/4.ans。

该样例满足测试点 10∼12 的约束条件。

样例 5

见题目目录下的 string/5.in 与 string/5.ans。

该样例满足测试点 13∼16 的约束条件。

样例 6

见题目目录下的 string/6.in 与 string/6.ans。

该样例满足测试点 19∼21 的约束条件。

数据范围

对于所有测试数据，均有：

• 1≤n≤2×105；
• 对于所有 i (1≤i≤n)，均有 1≤ai​≤109，且 ci​ 为小写英文字母。

测试点编号	n≤	maxi=1n​ai​≤
1	1	5
2∼4	2
5,6	10	1
7,8		50
9	2000	1
10∼12		50
13∼16		109
17,18	2×105	1
19∼21		500
22∼25		109

思路：

用pair存输入，记录l=1,r=n;

再进行消除（从两边，不一样累加ans)

代码：

#include<bits/stdc++.h>
#define int long long
#define db double
#define st string
#define ch char
#define bo bool
#define s2 105
#define s3 1005
#define s4 10005
#define s5 200005
#define s6 1000005
#define s7 100000005
using namespace std;
pair<int,char> a[s5];
int n;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    int l=1,r=n;
    int ans=0;
    while(l<r){
        int t=min(a[l].first,a[r].first);
        if(a[l].second!=a[r].second){
            ans+=t;
        }
        a[l].first-=t;
        a[r].first-=t;
        if(a[l].first==0) l++;
        if(a[r].first==0) r--;
    }
    cout<<ans;
    return 0;
}

我进了-S没进-J何意味

我CSP-J初赛就差了0.5分(;´༎ຶД༎ຶ`)

何意味！！！！！！！！！！！！！！