ACM练习7分治----（A - Median，B - Pie， E - Evil Straw Warts Live ）你的忏悔或许会让你心安，但未必别人如此。

101 阅读 0 评论 67 点赞

我是靠谱客的博主怡然玉米，最近开发中收集的这篇文章主要介绍ACM练习7分治----（A - Median，B - Pie， E - Evil Straw Warts Live ）你的忏悔或许会让你心安，但未必别人如此。，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

你的忏悔或许会让你心安，但未必别人如此。

Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.

Input

The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, ... , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

Output

For each test case, output the median in a separate line.

Sample Input

Sample Output

1
8

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int N,M,s[100010];
int jc(int x)
{
    int sum=0;
    for(int i=0; i<N; i++)
        sum+=(upper_bound(s+i,s+N,s[i]+x)-1-(s+i));//满足差值<=x的对数
    if(sum>=M)
        return 1;
    return 0;
}
int ef(int l,int r)
{
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(jc(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    while(~scanf("%d",&N))
    {
        int sum=N*(N-1)/2;
        if(sum%2==0)
            M=sum/2;
        else
            M=sum/2+1;
        for(int i=0; i<N; i++)
            scanf("%d",&s[i]);
        sort(s,s+N);
//        int l=0,r=s[N-1]-s[0];
        int jg=ef(0,s[N-1]-s[0]);
        printf("%dn",jg);
    }
    return 0;
}

My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.

My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size.

What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

Input

One line with a positive integer: the number of test cases. Then for each test case:

One line with two integers N and F with 1 ≤ N, F ≤ 10 000: the number of pies and the number of friends.
One line with N integers ri with 1 ≤ ri ≤ 10 000: the radii of the pies.

Output

For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10 −3.

Sample Input

3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

Sample Output

25.1327
3.1416
50.2655

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define wc 1e-5
typedef long long ll;
using namespace std;
int N,F,T;
double R[10010];
int pd(double x){
    int ct=0;
    for(int i=1;i<=N;i++){
        ct+=(int)(R[i]/x);//当前馅饼够几人分
        if(ct>=F)
            return 1;
    }
    return 0;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&F);
        F++;//还有本人
        double l=0.0,r=0.0;
        for(int i=1;i<=N;i++){
            scanf("%lf",&R[i]);
            R[i]=R[i]*R[i]*pi;
            r=max(R[i],r);
        }
        while(r-l>wc){
            double mid=(l+r)/2.0;
            if(pd(mid))
                l=mid;
            else
                r=mid;
        }
        printf("%.4lfn",l);
    }
    return 0;
}

A palindrome is a string of symbols that is equal to itself when reversed. Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols. For example, the string "mamad" may be transformed into the palindrome "madam" with 3 swaps:
swap "ad" to yield "mamda"
swap "md" to yield "madma"
swap "ma" to yield "madam"

Input

The first line of input gives n, the number of test cases. For each test case, one line of input follows, containing a string of up to 8000 lowercase letters.

Output

Output consists of one line per test case. This line will contain the number of swaps, or "Impossible" if it is not possible to transform the input to a palindrome.

Sample Input

3
mamad
asflkj
aabb

Sample Output

3
Impossible
2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int vis[40],fg[8010],cd,T,sum,flag,tail;
string s;
char ch;
void pd(){//判断是否能变成回文，有一个字母是奇数或者一个都没有
    int ct=0;
    for(int i=0;i<cd;i++)
        vis[s[i]-'a']++;
    for(int i=0;i<26;i++){
        if(vis[i]%2==1){
            ct++;
            if(ct==2){
                flag=0;
                break;
            }
            ch=i+'a';
        }
    }
}
void jh(){//统计交换的次数，从第一个字母开始从后往前找与它相同得字母放到最后即匹配成功
    for(int i=0;i<cd/2;i++){
        for(int j=tail;j>=i+1;j--){
            if(s[j]==s[i]){
                fg[i]=1;
                sum+=tail-j;//移动次数
                for(int k=j;k<tail;k++)//找到匹配的字母后面的字母往前移
                    s[k]=s[k+1];
                tail--;
                break;//跳出接着找
            }
        }
    }
    if(cd%2==1){//有单个字母为奇数移到最中间
        for(int i=0;i<cd;i++){
            if(s[i]==ch&&fg[i]==0){
                sum+=cd/2-i;
                break;
            }
        }
    }
    if(flag==1)
        cout<<sum<<endl;
    else
        cout<<"Impossible"<<endl;
}
int main(){
    scanf("%d%*c",&T);
    while(T--){
        sum=0,flag=1;
        memset(vis,0,sizeof(vis));
        memset(fg,0,sizeof(fg));
        cin>>s;
        cd=s.size();
        tail=cd-1;
        pd();
        jh();
    }
    return 0;
}