| |
常用鏈接
留言簿(4)
隨筆分類
隨筆檔案
搜索
最新評論
閱讀排行榜
評論排行榜
Powered by: 博客園
模板提供：滬江博客
|
|
|
|
|
發(fā)新文章 |
|
 |
題目是快速排序，可用的居然是合并排序，排序中計算逆序數(shù)即可。。。
 #include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
long long int count;
void Merge(long long int a[],long long int p,long long int k,long long int q)
   {
 long long int num1=k-p+1;
long long int num2=q-k;
long long int i;
long long int* b1=new long long int[num1+1];
long long int* b2=new long long int[num2+1];
for (i=0;i<num1;i++)
  {
b1[i]=a[p+i];
 }
b1[i]=9999999999;
for (i=0;i<num2;i++)
{
b2[i]=a[k+i+1];
}
b2[i]=9999999999;
int j=0;i=0;
for(long long int kk=p;kk<=q;kk++)
{
if (b1[i]<=b2[j])
{
a[kk]=b1[i];
i++;
}
else
{
a[kk]=b2[j];
j++;
count+=(num1-i); //求逆序數(shù)，即若b中有元素比a小，插入后共有a數(shù)組大小減去當前指向a的位置個逆序
}
}
delete [] b1;
delete [] b2;
 }
void MergeSort(long long int a[],long long int p,long long int q)
{
if (p<q)
{
long long int k=(p+q)/2;
MergeSort(a,p,k);
MergeSort(a,k+1,q);
Merge(a,p,k,q);
}
}
int main()
{
long int num;
while (scanf("%ld",&num)!=EOF&&num)
{
long long int* input=new long long int[num];
count=0;
for (int i=0;i<num;i++)
{
scanf("%lld",&input[i]);
}
MergeSort(input,0,num-1);
printf("%lld\n",count);
delete [] input;
}
}
很簡單的一道題，先從小到大排序，依次比較最小值*當前繩子數(shù)目，得出最大值
#include "stdio.h"
#include "stdlib.h"
long rope[10001];
int cmp(const void *a,const void *b)
{
long *x=(long *)a;
long *y=(long *)b;
return *x-*y;
}
int main()
{
int t,m,i,j;
long max;
scanf("%d",&t);
while(t--)
{
max=0;
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%d",&rope[i]);
qsort(rope,m,sizeof(long),cmp);
for(j=m,i=0;j>0;i++,j--)
{
if(max < rope[i] * j )
max = rope[i] * j;
}
printf("%ld\n",max);
}
return 0;
}
最爛的算法，先按大小排序，從最大的開始，如果不在最底，則先換到最上再換到最下，依次進行。。 還要注意數(shù)組越界問題，比如記錄次數(shù)的數(shù)組大小可能為2*n-3.。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100],b[100],n;
bool big(int x,int y)
{
return x>y;
}
int main()
{
int i,j;
while(scanf("%d",&n)&&n)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
reverse(&a[1],&a[n+1]);
int tmp[100]={0},tp=1;
for(i=1;i<=n;i++)
b[i]=a[i];
sort(b+1,b+n+1,big);
for(i=1;i<=n;i++)
{
for(j=n;j>=i;j--)
{
if(b[i]==a[j])
{
if(i==j)
;
else
{
if(j!=n)
{
tmp[tp++]=n-j+1;
tmp[tp++]=n-i+1;
reverse(&a[j],&a[n+1]);
reverse(&a[i],&a[n+1]);
}
else
{
tmp[tp++]=n-i+1;
reverse(&a[i],&a[n+1]);
}
}
break;
}
}
}
printf("%d",tp-1);
for(i=1;i<tp;i++)
printf(" %d",tmp[i]);
printf("\n");
}
return 0;
}
PS：還有個算法 設flip(k)是將前k個數(shù)反轉的操作 就以sample output第二個為例，43251 從最大數(shù)放起，先放5 在放5之前看4在不在5前面的數(shù)里，如果不在就不管他了，只處理5一個數(shù)，把它放到最后去 實際上是4在5前面，則先flip(3)讓4緊挨5，變成23451 然后看3在不在4前面，在，并且正好緊鄰 2同上 看1在不在2前面，不在，所以這次處理就處理到2，flip(4);flip(5)把2345放到最后去，變成12345 然后處理1，它已經(jīng)在該在的位置，結束
cin.getline()方法連續(xù)地從用戶終端接受字符，并將字符存入字符型數(shù)組message中，直到輸入了（maxchars－1）個字符（第maxchars個字符用來存儲字符串結尾的NULL字符'\0')或者接受到了回車為止，這終端鍵入回車鍵產(chǎn)生一個換行'\n'，它被cin.getline()認為是行輸入結尾。cin.getline()獲得的字符(除了換行符外)被存儲到message數(shù)組中。在返回之前，cin.getline（）函數(shù)在存儲的這些字符后面添加一個NULL字符'\0'。
Cin.ignore（）方法cin.ignore( 5, 'c' ) 的是從輸入流（cin）中提取字符，提取的字符被忽略（ignore），不被使用。每拋棄一個字符，它都要計數(shù)和比較字符：如果計數(shù)值達到5或者被拋棄的字符是'c'，則cin.ignore() 函數(shù)執(zhí)行終止；否則，它繼續(xù)等待。 它的一個常用功能就是用來清除以回車結束的輸入緩沖區(qū)的內容，消除上一次輸入對下一次輸入的影響。比如可以這么用：cin.ignore( 1024, '\n' );，通常把第一個參數(shù)設置得足夠大，這樣實際上總是只有第二個參數(shù) '\n' 起作用，所以這一句就是把回車（包括回車）之前的所以字符從輸入緩沖（流）中清除出去。
Cin.clear用法如果輸入發(fā)生錯誤發(fā)生，那么流狀態(tài)既被標記為錯誤，你必須清除這些錯誤狀態(tài)，以使你的程序能正確適當?shù)乩^續(xù)運行。要清除錯誤狀態(tài)，需使用clear()函數(shù)。此函數(shù)帶一個參數(shù)，它是你將要設為當前狀態(tài)的標志值。，只要將ios::goodbit作為實參
其實就是實系數(shù)多項式分解定理!n>=1的實系數(shù)多項式在實數(shù)域上都可以分解成一次因式與二次不可約因式的乘積!
在實數(shù)域上，奇次一定有一個根，偶次有共軛虛根,總是可以分解成兩個n/2的多項式。
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int a,b,c,n;
while(cin>>n)
{
if(n<2)
{
while(n>=0)
{
n--;
cin>>a;
}
cout<<"YES"<<endl;
}
else if(n==2)
{
cin>>a>>b>>c;
if(b*b>=4*a*c)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
else
{
while(n>=0)
{
n--;
cin>>a;
}
cout<<"NO"<<endl;
}
}
return 0;
}
|
|