hdu 1423 最長上升公共子序列 LCIS 模板題

累死我了。

開始的時候我因為題目沒有看清楚，沒有注意到計算結果超出了int，提交一直wa。看了別人的代碼，意識到了精度的問題，但是提交還是一直wa。沉默良久，想到了是在qsort排序的時候，在排序函數內部的值也會超出int，大喜，修改之後提交，依然wa……用sort函數排序，提交ac。

我很疑惑，不明白為什麼用sort提交通過，用qsort提交就wa。在編譯的時候，編譯器報警，我看了一下警告信息，突然意識到了qsort的比較函數是默認的返回int值，下面就知道怎麼處理了，跟double一樣，返回值不是int，那就換一種方式將int表示出來。

修改之後提交ac。

用sort提交的代碼：

?#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<iostream>  
#include <algorithm>  
using namespace std; 
#define N 100005  
struct node 
{ 
    long long x; 
    long long y; 
} a[N]; 
bool operator < (const node &a, const node &b) 
{ 
    return a.x * b.y <a.y * b.x; 
} 
int main() 
{ 
    int n; 
    int m=365*24*60*60; 
    while(scanf("%d",&n),n) 
    { 
        int i; 
        for(i=0; i<n; i++) 
            scanf("%I64d%I64d",&a[i].x,&a[i].y); 
        sort(a,a+n); 
        long long sum; 
        sum=0; 
        for(i=0; i<n; i++) 
        { 
            sum+=sum*a[i].y+a[i].x; 
            sum%=m; 
        } 
        printf("%I64d\n",sum); 
    } 
    return 0; 
} 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include <algorithm>
using namespace std;
#define N 100005
struct node
{
    long long x;
    long long y;
} a[N];
bool operator < (const node &a, const node &b)
{
    return a.x * b.y <a.y * b.x;
}
int main()
{
    int n;
    int m=365*24*60*60;
    while(scanf("%d",&n),n)
    {
        int i;
        for(i=0; i<n; i++)
            scanf("%I64d%I64d",&a[i].x,&a[i].y);
        sort(a,a+n);
        long long sum;
        sum=0;
        for(i=0; i<n; i++)
        {
            sum+=sum*a[i].y+a[i].x;
            sum%=m;
        }
        printf("%I64d\n",sum);
    }
    return 0;
}

用qsort提交的代碼：

#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<iostream>  
#include <algorithm>  
using namespace std; 
#define N 100005  
struct node 
{ 
    long long x; 
    long long y; 
} a[N]; 
int cmp(const void *a,const void *b) 
{ 
    return (*(node *)a).x*(*(node *)b).y>(*(node *)b).x*(*(node *)a).y?1:-1; 
} 
int main() 
{ 
    int n; 
    int m=365*24*60*60; 
    while(scanf("%d",&n),n) 
    { 
        int i; 
        for(i=0; i<n; i++) 
            scanf("%I64d%I64d",&a[i].x,&a[i].y); 
        qsort(a,n,sizeof(a[0]),cmp); 
        long long sum; 
        sum=0; 
        for(i=0; i<n; i++) 
        { 
            sum+=sum*a[i].y+a[i].x; 
            sum%=m; 
        } 
        printf("%I64d\n",sum); 
    } 
    return 0; 
} 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include <algorithm>
using namespace std;
#define N 100005
struct node
{
    long long x;
    long long y;
} a[N];
int cmp(const void *a,const void *b)
{
    return (*(node *)a).x*(*(node *)b).y>(*(node *)b).x*(*(node *)a).y?1:-1;
}
int main()
{
    int n;
    int m=365*24*60*60;
    while(scanf("%d",&n),n)
    {
        int i;
        for(i=0; i<n; i++)
            scanf("%I64d%I64d",&a[i].x,&a[i].y);
        qsort(a,n,sizeof(a[0]),cmp);
        long long sum;
        sum=0;
        for(i=0; i<n; i++)
        {
            sum+=sum*a[i].y+a[i].x;
            sum%=m;
        }
        printf("%I64d\n",sum);
    }
    return 0;
}