#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 500010;
int a[N];

int main()
{
    int n;
    long double s;
    cin >> n >> s;
    for(int i = 1; i <= n; i ++) scanf("%d",&a[i]);

    sort(a + 1, a + n + 1);

    long double res = 0, avg = s / n;
    for(int i = 1; i <= n; i ++)
    {
        long double cur = s / (n - i + 1);
        if(a[i] < cur) cur = a[i];
        res += (cur - avg) * (cur - avg) / n;
        s -= cur;
    }

    printf("%.4Lf", sqrt(res));
    return 0;
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int N = 210;
string s,temp;
int T,n;

void update(int i)
{
    if(s[i] == 'B') s[i] = 'W';
    else s[i] = 'B';
}

bool check(char c)
{
    temp = s;

    vector<int> v;
    for(int i=0; i<n-1; i++)
    {
        if(s[i] != c)
        {
            update(i), update(i+1);
            v.push_back(i+1);
        }
    }

    if(s[n-1] != c)
    {
        s = temp;
        return false;
    }
    else
    {
        if(v.size() == 0)
        {
            puts("0");
        }
        else
        {
            s = temp;
            cout << v.size() << endl;
            for(auto elm : v) cout << elm << " ";
            cout << endl;
        }
        return true;
    }
}


int main()
{
    cin >> T;
    while(T--)
    {
        cin >> n >> s;
        if(!check('B') && !check('W')) puts("-1");
    }
    return 0;
}

[//]: # (打卡模板，上面预览按钮可以展示预览效果 ^^)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 110;
char start[N],last[N];

void turn(int i)
{
    if(start[i] == '*')
        start[i] = 'o';
    else
        start[i] = '*';
}


int main()
{
    scanf("%s",&start);
    scanf("%s",&last);

    int len = strlen(start);
    int res = 0;
    for(int i = 0; i < len - 1; i++)
    {
        if(start[i] != last[i])
        {
            turn(i);
            turn(i+1);
            res++;
        }
    }
    cout << res;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
#define x first
#define y second

typedef pair<double,double> PII;
const int N = 1010;
PII section[N];

bool cmp(pair<double,double> a, pair<double,double> b)
{
    return a.second < b.second;
}

int main()
{
    int n,d;
    cin >> n >> d;

    int xp,yp;
    int isfailed = false;
    for(int i=1; i<=n; i++)
    {
        scanf("%d %d",&xp,&yp);
        if(d < yp)
        {
            isfailed = true;
            break;
        }
        double len = sqrt(d * d - yp * yp);
        section[i] = {xp - len, xp + len};
    }

    if(isfailed) puts("-1");
    else
    {
        sort(section + 1,section + n + 1, cmp);

        double last = -1e20;
        int cnt = 0;
        for(int i=1; i<=n; i++)
        {
            if(last < section[i].x)
            {
                cnt++;
                last = section[i].y;
            }
        }

        cout << cnt;
    }
    return 0;
}

分析:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;


typedef long long LL;
const int N = 1000010;
int a[N];
LL c[N];

int main()
{
    int n;
    cin >> n;

    LL sum = 0;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        sum += a[i];
    }

    LL avg = sum / n;
    for(int i = n; i > 1; i--) c[i] = c[i+1] + avg - a[i];
    c[1] = 0;

    sort(c + 1,c + n + 1);

    LL res = 0;
    for(int i=1; i<=n; i++) res += abs(c[i] - c[(n+1)/2]);
    cout << res;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 100010;
int a[N];

int main()
{
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);

    sort(a,a+n);

    int mid;
    if(n % 2) mid = a[n + 1 >> 1];
    else mid = a[n / 2] + a[n / 2] + 1 >> 1;

    int res = 0;
    for(int i=1; i<=n; i++) res += abs(a[i] - mid);
    cout << res;

    return 0;
}

贪心和DP双解法

贪心

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;
int a[N];


int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++) scanf("%d",&a[i]);

    int res = 0;
    for(int i=0; i<n; i++)
    {
        if(a[i+1] > a[i])
         res += a[i+1] - a[i];
    }

    cout << res <<endl;
    return 0;
}

DP

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100010, INF = 1000000000;
int f[N][2],w[N];

int main()
{
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) scanf("%d",&w[i]);

    //因为f[0][1]是非法状态，所以要初始化为-INF
    f[0][1] = -INF;
    for(int i=1; i<=n; i++)
    {
        f[i][0] = max(f[i-1][0], f[i-1][1] + w[i]);
        f[i][1] = max(f[i-1][1], f[i-1][0] - w[i]);
    }

    cout << f[n][0];
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 100010;
int a[N],temp[N];

LL merge_sort(int l,int r)
{
    if(l >= r) return 0;
    int mid = l + r >> 1;
    //递归调用分别求左右两边的逆序对数量
    LL res = merge_sort(l,mid) + merge_sort(mid+1,r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) temp[k++] = a[i++];
        else
        {
            res += mid - i + 1;
            temp[k++] = a[j++];
        }
    }

    while(i <= mid) temp[k++] = a[i++];
    while(j <= r) temp[k++] = a[j++];

    for(int i=l,k=0; i<=r; i++,k++)
    {
        a[i] = temp[k];
    }
    return res;
}


int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++) scanf("%d",&a[i]);
    //归并排序求跨过mid的逆序对数量
    cout << merge_sort(0,n-1) <<endl;
    return 0;
}

思路

::::::::::::::::::::::::::::::::::
分批处理相同id的外卖店，用last数组存储最后一次接受订单的时间，分前后处理相同id，前面一段先减去没有订单的间隔时间，然后加上收到的订单数量*2并判断是否加入或者拿出优先队列，如果last[id]!=T的话，证明后面一段时间也是空闲的，所以要减去空闲的时间，并判断是否拿出优先队列；

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100010;
pair<int,int> order[N];

int st[N],score[N],last[N];
int n,m,T;

int main()
{
    cin >> n >> m >> T;
    for(int i=0; i<m; i++)
        scanf("%d %d",&order[i].first,&order[i].second);

    sort(order,order+m);    

    for(int i=0; i<m;)
    {
        int j = i;
        while(j < m && order[i] == order[j]) j++;
        int t = order[i].first, id = order[i].second, cnt = j - i;
        i = j;

        score[id] -= t - last[id] - 1;
        if(score[id] <= 3) st[id] = false;
        if(score[id] < 0) score[id] = 0;

        score[id] += cnt * 2;
        if(score[id] > 5) st[id] = true;

        last[id] = t;
    }

    for(int i=1; i<=n; i++)
    {
        if(last[i] < T)
        {
            score[i] -= T - last[i];
            if(score[i] <= 3) st[i] = false;
        }
    }

    int res = 0;
    for(int i=1; i<=n; i++) res += st[i];
    cout << res <<endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 5010;
int s[N][N];

int main()
{
    int n,r;
    cin >> n >> r;
    r = min(r,5001);

    //让边界和r一样大，防止r的边界大于数据范围
    int mx = r, ny = r;
    for(int i=0; i<n; i++)
    {
        int x,y,w;
        scanf("%d %d %d",&x,&y,&w);
        x++,y++;
        s[x][y] += w;
        mx = max(mx,x);
        ny = max(ny,y);
    }

    for(int i=1; i<=mx; i++)
        for(int j=1; j<=ny; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + s[i][j];

    int res = 0;
    for(int i=r; i<=mx; i++)
        for(int j=r; j<=ny; j++)
            res = max(s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r], res);

    cout << res << endl;
    return 0;
}