cf627 div3

https://codeforces.com/contest/1324

 题意：

t组样例每组一个字符串 只有L,R组成

字符串从1到n青蛙从0开始，能到n + 1 的最大的d

如果是L,往左 ；如果是 R， 往右；保证青蛙从0走到最右面

逆向思维，加入一个点R，求相邻两个R之间距离的最大值

#include <bits/stdc++.h>
using namespace std;

int t,ans;
string s;
int main(){
    //freopen("in","r",stdin);
    ios::sync_with_stdio(0);
    cin >> t;
    while(t--){
        ans = 0;
        cin >> s;
        int l = s.size();
        s[l] = 'R';
        int pos = l;
        for(int i = l - 1; i >= 0; i--){
            if(s[i] == 'R'){
                ans = max(ans,pos - i);
                pos = i;
            }
        }
        if(s[0] != 'R')
            ans = max(ans,pos + 1);
        cout << ans << endl;
    }
    return 0;
}

 

(ai - bi) + (aj - bj) > 0

把a与b的每项做差，差值从小到大排序，从最大的r开始找，如果第一项和最大的相加 < 0,项数是r - 1;以此类推

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
int n,a[maxn],g;
int ans;
signed main(){
   //freopen("in","r",stdin);
    ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> g,a[i] -= g;
    sort(a + 1, a+ n + 1);
    int l = 1, r = n;
    while(a[r] > 0 && l < r){
        while(a[l] + a[r] <= 0)
            l++;
        if(l >= r)
            break;
        ans+= (r - l);
        r--;
    }
    cout << ans;
    return 0;
}