| |
常用鏈接
留言簿(4)
隨筆分類
隨筆檔案
搜索
最新評論
閱讀排行榜
評論排行榜
Powered by: 博客園
模板提供：滬江博客
|
|
|
|
|
發新文章 |
|
 |
題目是快速排序，可用的居然是合并排序，排序中計算逆序數即可。。。
 #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); //求逆序數，即若b中有元素比a小，插入后共有a數組大小減去當前指向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;
}
}
很簡單的一道題，先從小到大排序，依次比較最小值*當前繩子數目，得出最大值
#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;
}
最爛的算法，先按大小排序，從最大的開始，如果不在最底，則先換到最上再換到最下，依次進行。。 還要注意數組越界問題，比如記錄次數的數組大小可能為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個數反轉的操作 就以sample output第二個為例，43251 從最大數放起，先放5 在放5之前看4在不在5前面的數里，如果不在就不管他了，只處理5一個數，把它放到最后去 實際上是4在5前面，則先flip(3)讓4緊挨5，變成23451 然后看3在不在4前面，在，并且正好緊鄰 2同上 看1在不在2前面，不在，所以這次處理就處理到2，flip(4);flip(5)把2345放到最后去，變成12345 然后處理1，它已經在該在的位置，結束
cin.getline()方法連續地從用戶終端接受字符，并將字符存入字符型數組message中，直到輸入了（maxchars－1）個字符（第maxchars個字符用來存儲字符串結尾的NULL字符'\0')或者接受到了回車為止，這終端鍵入回車鍵產生一個換行'\n'，它被cin.getline()認為是行輸入結尾。cin.getline()獲得的字符(除了換行符外)被存儲到message數組中。在返回之前，cin.getline（）函數在存儲的這些字符后面添加一個NULL字符'\0'。
Cin.ignore（）方法cin.ignore( 5, 'c' ) 的是從輸入流（cin）中提取字符，提取的字符被忽略（ignore），不被使用。每拋棄一個字符，它都要計數和比較字符：如果計數值達到5或者被拋棄的字符是'c'，則cin.ignore() 函數執行終止；否則，它繼續等待。 它的一個常用功能就是用來清除以回車結束的輸入緩沖區的內容，消除上一次輸入對下一次輸入的影響。比如可以這么用：cin.ignore( 1024, '\n' );，通常把第一個參數設置得足夠大，這樣實際上總是只有第二個參數 '\n' 起作用，所以這一句就是把回車（包括回車）之前的所以字符從輸入緩沖（流）中清除出去。
Cin.clear用法如果輸入發生錯誤發生，那么流狀態既被標記為錯誤，你必須清除這些錯誤狀態，以使你的程序能正確適當地繼續運行。要清除錯誤狀態，需使用clear()函數。此函數帶一個參數，它是你將要設為當前狀態的標志值。，只要將ios::goodbit作為實參
其實就是實系數多項式分解定理!n>=1的實系數多項式在實數域上都可以分解成一次因式與二次不可約因式的乘積!
在實數域上，奇次一定有一個根，偶次有共軛虛根,總是可以分解成兩個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;
}
|
|