yuanbin

yuanbin
10个月前

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N],n,i,ans,sum;
int main()
{
cin>>n;
for (i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int sm=a[n/2+1];
for (i=1;i<=n;i++)
ans=ans+abs(a[i]-sm);
cout<<ans;
return 0;
}


yuanbin
10个月前
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e5+100;
int r[N],a[N],n;
long long ans=0;
void msort(int s,int t)
{
if(s==1&&t==n) ans=0;
if(s>=t) return;
int mid=(s+t)/2;
msort(s,mid);msort(mid+1,t);
int i=s,j=mid+1,k=s;
while(i<=mid&&j<=t)
if(a[i]<=a[j]) r[k++]=a[i++];
else
{
r[k++]=a[j++];
ans+=mid-i+1;
}
while(i<=mid) r[k++]=a[i++];
while(j<=t) r[k++]=a[j++];
for(int i=s;i<=t;i++) a[i]=r[i];
}
int main()
{
while(cin>>n&&n)
{
for(int i=1;i<=n;i++) cin>>a[i];
msort(1,n);
cout<<ans<<endl;
}
return 0;
}



yuanbin
10个月前
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
vector<int> specialSort(int n) {
vector<int> res;
res.push_back(1);
for (int i = 2; i <= n; i ++ )
{
int l = 0, r = res.size() - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (compare(res[mid], i)) l = mid;
else r = mid - 1;
}
res.push_back(i);
for (int j = res.size() - 2; j > r; j -- ) swap (res[j], res[j + 1]);
if (!compare(res[r], i)) swap(res[r], res[r + 1]);
}
return res;
}
};



yuanbin
10个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<math.h>
using namespace std;
const int N = 100010 ;
int height[N];
double cpy[N];
double cpy_sum[N];
bool check(double target,int n, int f){

for(int i =1;i<=n;++i)
cpy[i] = height[i];

for(int i =1;i<=n;++i)
cpy[i] -= target;
memset(cpy_sum,0,sizeof(cpy_sum));

double min_left = 1<<30;
double max_res = -10000000000;
for(int i = 1;i<=n;++i){
cpy_sum[i] = cpy[i] +cpy_sum[i-1];

if(i-f>=0){
min_left = min(cpy_sum[i-f],min_left);

max_res = max(max_res,cpy_sum[i]-min_left);
}
}

return max_res >=0.0;

}
int main(){

int n ,f;
cin >> n >>  f;
int sum = 0;
for(int i = 1;i<=n;++i){
cin >> height[i];
sum += height[i];
}

double left = 0.0,right = 2000;
const double eps = 1e-7;

while(right- left > eps){
double mid = (left+right)/2.0;
if(check(mid,n,f))
left = mid;
else
right = mid;
}

cout << (int)(right * 1000) <<endl;

return 0;
}


yuanbin
10个月前
#include<iostream>
#include<stdio.h>
#include<set>
using namespace std;
const int N = 1000010;
int heights[N];
set<pair<int,int>> visit;

int main(){
int n ,p,h,m;
cin >> n >> p >> h >> m;
heights[1] = h;

for(int i = 1,a,b;i<=m;++i){
cin >> a>>b;
if(a>b) swap(a,b);
if(!visit.count({a,b})){
visit.insert({a,b});
heights[a+1]--, heights[b]++;
}
}

for(int i =1;i<=n;++i){
heights[i] += heights[i-1];
cout <<heights[i]<<endl;
}

return 0;
}



yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
using  namespace std;
const int N = 500005;
typedef long long LL;
long long  a[N],b[N];

int main(){
int n ;
cin >> n;
for (int i = 1; i <= n; i ++ )
cin >> a[i];
memset(b,0,sizeof(b));

for (int i = 1; i<=n; i ++ )
b[i] = a[i] - a[i-1];

LL p=0,q=0;
for(int i =2;i<=n;++i)
if(b[i]>0)
p+=b[i];
else
q-=b[i];
cout << max(p,q) <<endl;
cout <<abs(p-q)+1<<endl;

return 0;
}


yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
const int MAX = 5005;
int sum[MAX][MAX];

int main(){
memset(sum,0,sizeof(sum));

int N,R;
cin >> N>>R;
for(int i = 1;i<=N;++i){
int x,y,v;
cin >> x>>y>>v;
sum[x+1][y+1] += v;
}

for(int x = 1;x<=5000;++x)
for(int y=1;y<=5000;++y)
sum[x][y] += sum[x-1][y] + sum[x][y-1] - sum[x-1][y-1] ;
int value = 0;
for(int i = R;i<=5000;++i){
for(int j = R;j<=5000;++j){
int cur = sum[i][j] - sum[i-R][j] - sum[i][j-R] + sum[i-R][j-R];
value = max(cur,value);
}
}
cout << value <<endl;

return 0;
}


yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<math.h>
using namespace std;
const int MAX = 2000000;
bool dp[7][MAX];

int main(){
while(true){

int number[7];
for(int i = 1;i<=6;++i)
cin >> number[i];
int sum = 0;

for(int i = 1 ;i<=6;++i)
sum += number[i]*i;
if(!sum) break;

if(sum % 2 == 1){
cout <<"Can't" <<endl;
continue;
}

int half_sum = sum/2;
memset(dp,false,sizeof(dp));
dp[0][0] = true;

for(int i = 1;i<=6;++i){
int maxdepth = 0;
int s=  number[i];
while(s){
maxdepth +=  1;
s = s >> 1;
}
for(int v = 0;v<=half_sum;++v){
dp[i][v] = dp[i-1][v];

for(int k = 0;k<maxdepth && v-(int)pow(2,k)*i>=0;++k){
dp[i][v] = dp[i][v] | dp[i][v-(int)pow((int)2,k)*i];
}
}
}

if(dp[6][half_sum])
cout << "Can" <<endl;
else
cout <<"Can't" <<endl;
}

return 0;
}


yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;

const int N = 205;

int a[N], last[N], pre[N], f[N][N][N];
int dp(int l,int r, int k){
if(l>r) return 0;
if(f[l][r][k]) return f[l][r][k];

if(a[r-1]^a[r]) f[l][r][k] = max(f[l][r][k], dp(l,r-1,0)+(k+1)*(k+1));

for(int i = pre[r];i>=l;i = pre[i])
f[l][r][k] = max(f[l][r][k],dp(l,i,k+1)+dp(i+1,r-1,0));

return f[l][r][k];
}

int main(){
int t;
cin >> t;
int num = 1;
while(t--){
int n;
cin >> n;
memset(last,0,sizeof(last));
memset(a,0,sizeof(a));
memset(pre,0,sizeof(pre));
memset(f,0,sizeof(f));

for(int i = 1;i<=n;++i){
cin >> a[i];
pre[i] = last[a[i]];
last[a[i]] = i;
}
int res = dp(1,n,0);
cout<<"Case "<<num++<< ": "<< res <<endl;

}

return 0;
}


yuanbin
11个月前
#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<math.h>
using namespace std;
int matrix[20][20];
int sum[20][20];
int dp[10][10][10][10][20];
const int inf = 100000000;

int qry(int x1, int x2,int y1, int y2){
return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
}

int area(int x1,int x2, int y1, int y2, int t){
if(dp[x1][x2][y1][y2][t] != 0)
return dp[x1][x2][y1][y2][t];

if(t == 1)
return qry(x1,x2,y1,y2) * qry(x1,x2,y1,y2);

if( x1 == x2 && y1 == y2)
return inf;
int ans = inf;

for(int x = x1;x<x2;++x){
int row1 = area(x1,x,y1,y2,1)+area(x+1,x2,y1,y2,t-1);
int row2 = area(x1,x,y1,y2,t-1)+area(x+1,x2,y1,y2,1);
int res = min(row1,row2);
ans = min(res,ans);
}

for(int y = y1;y<y2;++y){
int col1 = area(x1,x2,y1,y,1)+area(x1,x2,y+1,y2,t-1);
int col2 = area(x1,x2,y1,y,t-1)+area(x1,x2,y+1,y2,1);
int res= min(col1,col2);
ans = min(ans,res);
}

dp[x1][x2][y1][y2][t] = ans;
return ans;
}

int main(){
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));

int n ;
cin >> n;
for(int i = 1;i<=8;++i){
for(int j = 1;j<=8;++j){
cin >> matrix[i][j];
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i][j];
}
}

double avg = (double)sum[8][8]/n;

int fang = area(1,8,1,8,n);

double res = sqrt( (double)(fang-n*avg*avg )/n );
printf("%.3f\n",res);

return 0;
}