| |
常用链接
留言簿(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;
}
|
|